Bat-In-The-Attic's well-known How To Make A Fantasy Sandbox posts start with the geography and build up from there. Personally, I start with the kind of game I've got and bend the geography to that. Here's how I'd go about it.
1. Decide where the players are going to start. You have two options for where the PCs start--1. Awesome, 2. Not awesome.
If your players start in a place that's awesome, then that means you just start off the game with something interesting happening like they are escaping the hold of a pirate ship or fighting a dire weasel with numchuks for arms. If your players start off in a place that's not awesome the idea is they leave this tedious hole for something more interesting in session 1.
The advantage of having them start someplace awesome is the first thing the PCs get is something awesome.
The advantage of having them start in someplace not awesome is the first thing the PCs get is a choice about where they have their first adventure.
A third way is to have the PCs starts someplace not awesome but give them a clear and present awesome objective that is strongly implied--which is the traditional way to start these games. Like you live in Safington and yet it is in the shadow of Notasboringasyourtown Dungeon. I myself am not a fan of this approach but, hey, whatever.
2. Write the first adventure. Wait, what, I thought this was a sandbox-building guide? Ok, it is, but--trust me--this is a crucial first step. Write enough material for that first adventure, either:
A) the awesome place they've woken up in and its immediate environs or
B) the awesome place they're heading to plus--if you want--the dead hex space between non-awesome and awesome, the pirate-ship they're escaping. Or just have enough moving parts in the immediate environs to fill up an evening's worth of play.
3. Decide PC options. Any races or classes out? Any new ones in? Decide now. If you have setting ideas about races or classes ("All elves have french names""Bards are hunted for their meat" or whatever) feel free to integrate them now.
4. Run the first adventure. Wait, there's no world yet? Calm down. It'll be ok.
5. Be All "That was fun", Then Decide Where Everyone & Everything In It Was From Like you likely had 2-7 PCs and some treasure and maybe an item and a monster or two and villains. Decide where each one of these things was from--the name isn't as important as the basic description, like the goblin was from "A jewelled-encrusted prison colony in the mysterious East", and the druid was from "a pleasant, misty rural community with a quiet sideline in human sacrifice". You should probably check with your players that the basic idea s you have about their origins are ok if they're high strung and/or if you think they'll have anything interesting to add.
6. Decide Which Other Races Have Their Own Civilizations In Your Campaign: Like maybe their weren't any gnolls in that first adventure but you want there to be a gnoll empire. Look through the monster manual and your notes and decide which of these cultures is organized and separate from the main civilization. Of course you have the option to have none and have it all be human-dominated or the option to have it be a continent-wide mixed-race egalitarian civilization, too--though some of us do prefer to enjoy life.
7. Decide Which Of These Places from 5 and 6 Will Be On The Map Some of these places may be so far away that you don't imagine the PCs being able to reach them in the early phases of the game, or at least the course of the game as you originally conceive it. Some will. Make a list of those that will.
8. Decide Which Moods or Subgenres You May Want To Shoehorn Into This Game And Make Up Some Place Names That Fit Them ...castles brimming with Arthurian intrigue, creepy fairy tale places, old school orclands, a lost continent of fucked-up dinosaurs, gritty Harnisms...Make up at least one place name for an area or city that will definitely feature that kind of action. Do you want a Grimdark Warhammer Wilderness? Figure out a name for those woods (Skurnvort Wald--there you go). Do you want a city of Vancian lunatics? Name it. Write these names down on the list with the list from step 7.
9. Decide Any Other Places That You Want On The Map Anything--old dungeons you have lying around, geographical features, locations from modules, cities where you just thought up a name and liked it, et cetera. Write those on the list, too.
10. Use Your Place List To Make A Hybridizing Chart Like This: Use this to decide interrelationships between various areas. Does the gnoll kingdom trade with the Duchy of Skrogglehorn? Do the Engine Lords know about the Dungeon beneath Growgorn Gap? You do not have to think of a relationship for every single location to every other, but the more you think up, the more adventure fuel you've got. When you're done, write down everything you think you might forget about each place.
11. Now Get Out A Big Piece of Paper And Decide Where Your PC Start Point Is You got basically two choices here: either the PC start point is in the middle or it's not.
If it's not, you have to establish that the PC start point is backed up against some basically impassable geographic barrier that keeps the PCs from going off the map (like the Atlantic Ocean in stories where intrepid Americans head west to find adventure) or you have to convince the players that everything off the edge of the map is boring for some reason. Middle is the simplest.
12. Look At Your Chart From Step 10 And Decide What The "Travel Notes" To Those Locations From The Start Point Would Look Like No doubt by this point you've decided some places are far distant indeed from the quiet little Shire/pirate ship hold/cretinous backwater where your PCs started out and will require a lot of travel, some are close, some may require a sea journey and some you don't care yet. Make some lists: Close, Far, Middle (maybe), Sea Journey, Mountains, and Don't Care Yet.
13. Look At The "Far" List And Put Those Places On The Map Decide how far those places are from each other--is one far North, one South, one East and one West? Put them on the map with little dots.
14. Do The Same With The Other Lists It's best to start with the furthest places and move inward. If you know something will require a sea journey or traversing mountains or deserts, pencil those in, but remember--pencil for now.
15. Do This To Figure Out Your Hex Scale.
16. Fill In Hexes On The Map Or Just Make A Note Of The "Hexes-Per-Inch" Rate Of Your Map
You have one distance you already found in step 15 so that should give you the scale of the whole map. You can use hexmapping software or draw hexes in or use an overlay or, actually, just put small colored dots at regular intervals (one where the center of each "hex" would be) on the map or whatever. Point is you now should have a map with places on it and with a scale and with hexes, too.
17. Make A Terrain List
Make a list of all the kinds of outdoor terrain that you think it's cool to watch PCs fight in. Keep in mind that each form of terrain should have some horrific, dangerous thing that could happen during a fight associated with it--frozen ice on a lake could crack, a battle in a black forest could awaken sleeping (evil) treants, etc.
18. Fill In Terrain--Mountains And Rivers And What-All
Place geographical and topographical features on the map. Include every kind of cool terrain plus any uncool terrain necessary for verisimilitude.
Some people like using scientific projections to model realistic terrain (and here's a great link for them), but here's an additional consideration:
When PCs are traveling, remember that there isn't much point to even having a map unless destination to any other plausible destination nearby has more than one way to go and the PCs can see--before going--pros and cons to each route.
Now EVERY filled-in hexmap automatically presents PCs with choices like this: path A will take you through (say) 9 temperate mountain hexes and 3 tundra hexes and path B will take you through 5 temperate mountain hexes and 7 tundra hexes. However: this only affects the PCs decisions in an interesting way if they believe enough in the overall realism of the world and the GM's style that the odds of encountering something they'd rather not while traveling across terrain type A is actually significantly greater than that of traveling across terrain type B (i.e. their GM isn't gonna just throw a level-8 encounter in on the way to Cape Crowne no matter which way they go) AND that the difference isn't so obvious that it makes one path obviously so stupid that they'd never choose it.
The simplest way is: dangerous quick route, safer long route.
Some other options include: mysterious route, possibly slightly helpful but also possibly dangerous route, etc. etc.
Anyway, when choosing what terrain will go in what hex, consider that.
19. Make A Monsters-You-Aren't-Otherwise-Using List
Make a list of all the kinds of monsters (and opposing NPCs) that you think are cool. Cross off any ones you don't want randomly encountered.
20. Make A Chart With The Monsters/NPCs Along One Axis and The Types of Terrain Along The Other.
Place a mark every time you think it would be a pip to have the PCs fight that monster/NPC in that terrain. (For example: it is cool to encounter a pack of dire wolves on a frozen mountain-face, it is boring to encounter a basilisk in a cave.) Now you have a List of Wilderness Encounters.
21. Sort The Encounters By Terrain-type, See How Many You've Got, Add Some Detailed Ones.
For each type of terrain, make at least one encounter more detailed and add a triggerable event or adventure seed to it, for example: killing the wolves on the frozen mountain-face angers the Frost God Cor-Greth and causes the Blue Jewel of Cor-Greth to begin absorbing the souls of men. These are your Complicating Wilderness Encounters. The location of any macguffins in these seeds should be left vague until the encounter occurs, at which point the necessary macguffins will be as far from the PCs current stated objective as possible (the PC shouldn't be able to get to the city/town/location where the macguffin is without doing a day's worth of playing--this gives you time to write more stuff about it before the PCs get there.)
22. Sort Encounters By Goodness Within each terrain-type, sort all the encounters (detailed and un-detailed) by interestingness. This is the order in which you will spring the encounters on the party (unless some encounters have prerequisites for some reason), using the randomness number from step 15, you've determined whether there even is an encounter at all...
23. Stick Nonmonster, NonNPC Things In the Terrain Encounter Lists
Think of anything else that you might want the PCs to run into randomly
25. When You Get Ideas, Add New Stuff To Places PCs Haven't Been Yet Between Sessions
*Wikipedia: The primary advantage of a hex map over a traditional square grid map is that the distance between the center of each hex cell (or hex) and the center of all six adjacent hexes is constant. By comparison, in a square grid map, the distance from the center of each square cell to the center of the four diagonal adjacent cells it shares a corner with is greater than the distance to the center of the four adjacent cells it shares an edge with...The other advantage is the fact that neighbouring cells always share edges; there are no two cells with contact at only one point. (i.e. going southwest as opposed to south doesn't mean you have to imagine squeezing through a tiny corner of a square.)(But why not octagons? Octagons don't tessellate.)
“Naive” OD&D Underworld design
10 hours ago