I've used easel pads ever since I saw it done in a local game store. Great for reusing the maps when PCs retreat (no need to redraw!), preparing in advance, and so on.
I recommend drawing in crayon, since it doesn't bleed through the paper. Cheap color battle mats.
It's a bit pricy to buy up front, but once you have a stash, I think it works great.
You can buy them on Amazon.com, or from office max online, etc. Any office supply store should have them in stock too. For about twice the price, you can get ones with post it sticky backs so that you can leave the areas you've already been through posted on the wall instead of rolling them up, etc.
If anyone knows of a 1 inch hex grid easel pad, please post it.