I recently received an email from Nicolo, with a pulp mutants & sorcery campaign "The Doomed Wastelands" which also features further iterations of cactus people, who is an inexperienced DM with little sandbox experience asking advice on filling up a hexmap key.
How I keyed my map went in several stages: procedures
1) The Map. Certain locations immediately suggest and appropriate key entry for the hex, such a landmarks, ruins, and the like.
2) Ripping Off Others Work. I make a list of cool things to put in the map that are usually inspired by something from a fiction, history or real life, and put them where appropriate. When I'm working on a project like this I try to read a lot of good fantasy & sci-fi, comics and the like. This also includes pop culture/literature/genre/rpg "easter eggs". I add to the list when I come across something inspiring in a book or daydreaming.
3) Use the 1st edition AD&D Dungeon Masters Guide Random Wilderness Generation Appendix. I roll for every hex on the ruins/castles/settlements table, and if I get a result I like I put it in the hex. Larger settlements I usually arbitrarily make into ruins, smaller settlements can be outcast camps; fortified stockades; subterranean hidden enclaves and the like, with usually random determination for what kind of man/being inhabits it. For ruins and castles I follow the DMG guidelines for the generation of monster, human or high level NPC and entourage inhabitants.
4) Stock the Dungeon. I treat every hex as a dungeon room, generating it's contents in the same fashion as classic OD&D or B/X D&D.
For monster results I roll from one of several encounter tables from different editions/sources (OD&D; B/XD&D; AD&D; Gamma World; Carcosan Grimoire; etc, determination of which source being random as well), and I try to come up with a "Algolian" encounter from the result, altering the monster as I see fit to make it fit the campaign. Usually such results mean that the "monster" has a lair or building in the hex.
With treasure results there's treasure somewhere in the hex, either monster loot or stashed somewhere.
With trap results there's a hazard, such a spiked pits; areas without oxygen; toxic gases; irradiated water, and the like, located in the hex.
With Trick/Special results theres a wilderness equivalent of such dungeon phenomena, stuff like ability score altering fungi, altered gravity or glowing psychic crystal skull hologram oracles.
5) Roll for a random encounter in each hex, using the probabilities from B/XD&D or the Carcosan Grimoire, and roll from a randomly determined encounter table in the fashion of stage 4 above. I Algol-ize the results or reroll if I don't especially feel the result. I'll use the "%Liar" to determine whether any monsters are lair monsters or just passing through the hex.
6) Repeat stage 5 (and even 4) until the hex key feels dense enough.
ALSO MORE JOESKY!!
I'm down with JOESKY's words of wisdom. Enough hot air blather about the most recent iteration of Carcosa Gate/Porno Gate/et al and more monsters, houserules, and maps!
I've been doing a bunch of mapping lately with my sweet new tiny mapping-box. I've found the combination of a cheap school geometry set; an selection of cheap and high-quality mechanical pencils; an assortment of fine tip to larger markers; a palm-sized pad of graph paper; and a small lidded box to hold it all to be a great asset for dungeon mapping creativity, I'm practically shitting out small (yet actually covering a fair amount of 10' square ground!) dungeon maps. One of the benefits of these small maps is that I can easily stitch them together to generate larger dungeon maps with a nice "inconsistent grain" that also avoids the 8.5"x11" phenomenon of bog-standard dungeon mapping methodology.