I'm a fan of using a GIF I created with little icons for players, monsters, and terrain, and hosting the images on PhotoBucket (see the Map spoiler in
this thread, if you're able to view it). The downside is you have to manipulate it in a program like Paint, PhotoShop, or GIMP, and you have to save separate images as the terrain updates. Still, I like the flexibility.
You've done spreadsheets in the past. If they're labeled well enough, those work fine.