What my player and I did was purchase the DND Miniatures starter set. It came with minis and a paper "DND Battle Grid".
What I did with the Battle Grid was take it to Kinko's and got it lamented for $13-$16. It rolls up really well and transparency and dry-erase markers work great on it. Except for green, which leaves a green haze.
In addition, we got DND minis in the bargain. It's really interesting seeing the Halfling next to the Gnoll, heh. It's help in visualizing the actual size discrepancy.