When I started playing with AD&D 1E (in 1979 or 1980) we didn't use miniatures or battle maps, it was all theater of the mind. Since all the players I knew personally started with AD&D none of us had seen Chainmail or played miniatures games.
When I moved on to DragonQuest, 2nd edition, (in the mid 1980s) where a hex grid and miniatures was required, I bought a Chessex hex grid Megamat and wet erase markers. One of my brothers had bought a box of miniatures (though for the life of me I cannot remember what company it was from or what figures it contained). We used those for player characters. For monsters, I cut out a bunch of ¾ inch square blocks of wood and numbered them on the top side, put a “D” for Dead on the bottom side, put an “S” on another smooth side for Stunned, and a “U” for Unconscious, leaving the rough sides (where the wood was cut against the grain) blank. I continued to use all these when I moved over to using GURPS 3rd edition, which also had specific Stunned and and Unconscious conditions.
Much, much later I got the Steve Jackson Games Cardboard Heroes but never could bear to cut them up, since I wasn't actively playing at the time it came out (1999 or so?)
When I started playing D&D again with 3.5E (probably sometime after 2004) I mostly played and didn't DM. I was fortunate that the DMs that I played with had good collections of pre-painted plastic miniatures for both player characters and monsters from the Dungeons & Dragons Miniatures Game. I did collect some of the Dungeon Tiles (see wikipedia and dmdavid) that Wizards of the Coast published during this time. (I actually used them playing Savage Worlds.)
The one campaign that I DMed with 3.5E I bought an Flip Chart/Easel Pad printed with a 1 inch grid. I would take several sheets to the game in a tubular storage container and draw the rooms on the map with black marker as the players explored. If we ran off the the side of a sheet or went to a new level I'd get out another sheet and draw on that. This worked surprisingly well.
One GM had a fair bit of Dwarven Forge terrain and that was a lot of fun to play on.
When I started playing Savage Worlds (around 2005) I did a lot of GMing, and was thrilled by the Figure Flats and map tiles that that Great White Games (now known again as Pinnacle Entertainment Group — PEG) included in many of their Savage Tales PDF adventures. I had a printer that could print on card stock, so these were ideal for me. Later PEG products, such as their Plot Point campaigns, often had Figure Flats as separate PDF accessories. I found them all very useful.
I also found the e-Adventure Tiles series from SkeletonKey Games very useful. These geomorphic map tiles are 6×6 inch squares, marked with a 1 inch square grid, and by printing them out and putting them together you can produce an infinite variety of maps. I found them most useful when printed on cardstock and labeled on the back with their id number. I'd make up several maps and then sort out the printed tiles for that map into a manila envelope for easy retrieval. There used to be a program that you could use the small preview images from the tiles (which were considerately set up for easy Copy and Paste from the PDF) to lay out your map at the small scale and then print it for reference when later putting together the large tiles. 1 I'd include those in the manila envelope with the tiles.
I used paper miniatures from Arion Games and Disposable Heroes paper miniatures from Precis Intermedia. I also had Paper Wars - Dragon Pass at War, a collection of Glorantha paper miniatures published by The Unspoken Word, which seem to have been drawn by Simon Bray, Dario Corallo, and Sarah Evans.
A lot of the early paper miniatures that I used were tri-fold and were cut out, folded, and glued (or taped) together. They usually had front sides in color and a back side in black and white. Unfortunately, these take up almost as much room as lead or plastic miniatures, though were much lighter to carry. I stored them in cheap plastic food containers, which let me easily see what was inside them. Carrying enough of them to games outside my home was a bulky problem.
Eventually I moved to A-frame paper miniatures, where there are two sides and they are attached at the top, with tabs that fold out or in at the bottom for a base. Instead of relying on the tabs to form the base, I used plastic stands from Precis Intermedia, where you'd just fold the miniature once and stick it in the stand. The stands add a bit of weight to the miniatures and make them much more stable. If you cut out a front that is attached to a back, instead of all three sides, you can just fold them once and stick them in a stand as well, so I could use all my trifold paper miniatures as well.
(The Zen DIY Paper Miniatures Page has some pictures of A-frame and trifold paper miniatures.)
Since these paper miniatures are flat when not inserted into stands I currently organize my paper miniatures into separate small manila envelopes for each type of creature, labeled with the creature type on the outside. Occasionally I use small ziplock bags, especially for the PCs' miniatures.
The paper miniatures described above are all drawn in such a way that the figure is drawn within a rectangle and you can cut them out with long straight cuts and cross cuts. There is another style of paper miniatures drawn in a manner so that you cut out the irregular outline of the figure itself with many small or curving cuts. These are much harder to cut out, and are more difficult to store, but are very impressive to look at. (You can see some examples in the Monsters collection at One Monk Miniatures) That's too much work for me!
I also got a Steel Sqwire Flip Mat, which uses dry erase pens, and it is 24×30 inches and folds up into an 8×10 inch package only a ¼ inch thick or so. Much easier to carry around, since it fits into the same backpack or messenger bag I use to carry my RPG books and accessories. 2 More over, unlike the ones you can find now published by Paizo, it had both 1 inch squares and 1 inch hexes, perfect for DragonQuest, GURPS, or The Fantasy Trip, though I've used mostly the squared side, for Savage Worlds. The dry erase pens are much more satisfactory than the wet erase pens. For some time I haven't had extra time to lay out locations using paper map tiles, and the Flip Mat lets me quickly draw out locations.
While I usually use miniatures and a battle map for Savage Worlds there have been several occasions where I've run games in theater of the mind style, without any miniatures or battle map. It takes a little adapting, but isn't that difficult.
My current practice is to use paper miniatures in stands for player characters and numbered blocks for opponents, with a Flip Mat as the battle map. Some times for opponents that take up more than one square I'll fold over or cut up a 3×5 or 4×6 card and use that, writing an arrow to indicate which way is the front.
Of course, when running AD&D or B/X D&D or retro-clones there of (like Goblinoid Games's Labyrinth Lord (L1, L2), it's AD&D inspired Advanced Edition Companion, or the book that squashes them together: Advanced Labyrinth Lord, or like Necrotic Gnome's Old School Essentials, or Swords & Wizardry) it's all theater of the mind: no miniatures, no battle map.
The program that I used was a desktop application rather than a web-based application, but Tiamat the Tile Mapper is a similar application.
Dice of course; usually I carry a couple of extra sets for when someone forgets their dice. For Savage Worlds I carry several differently colored sets of glass beads (stored in small ziplock bags). I use blue beads for bennies, white beads for GM bennies, red beads for wounds, yellow beads for shaken and white beads again for fatigue. I've found it helps the players (and myself) to remember their status if they have physical objects sitting on their character sheet to remind them. When playing with numbered blocks for opponents I put the shaken bead on top of the block; this really helps when I've got 30 opponents on the table. I carry a couple of decks of playing cards for Savage Worlds initiative.