One of my major tools in building hex map, and associated setting, is the Second Rule of Dungeoncraft, from Ray Winniger's (excellent) Dungeoncraft column.
Every time I create an important part of my setting, I create a secret about what I just created, and I put it into the deck 'o secrets. (Yes, I use an actual 3x5 notecard. I'm just that hardcore.) When I need something new to put on the map I'll draw a card from the deck, and try to figure out a way to work a clue to that secret into an encounter. This and random generation is how about 90% of what's on the map found origin.
My process works a little differently from the specific one that Winniger describes, because I'm starting very locally, and working my way up from there. I didn't start working on the gods until I had clerics who needed those gods. So most of my secrets are about NPCs and locations rather than fundamental ways the world works.
Not that I don't have a few of those. But I did it backwards. I thought to myself, "I need a big, world-changing secret that I can work into the early part of the game." And then I came up with some ideas about how the metaphysics of the setting that would support that, and suddenly I've got a general framework for how the planes interact, a couple new gods, and a rough idea for both a true creation myth and a false one.