We use the Paizo Megamat which is 34 by 48 I think. The edges kind of hang over the table, so we don't use the full size of it, but it's big enough for most of our encounters. We use wet-erase markers to draw the rooms and such...
I build each map as needed from Dungeon Tiles. They can range anywhere from a simple 8x10 tavern to a sprawling 50x60 dungeon complex. I have a massive 5'x5' table for everyone to play on while my 3'x4' DM's table is separate.
I have a pretty big Chessex mat (not the mondo size, but respectable), but of late I've been pre-drawing maps on an Office Depot 1" graph flip-chart, which ends up being about exactly the right size for most maps.