But if a large area consists of forest, for instance, how do you create meaningful choices about where to explore?
Essentially, I do some top down design informed by random encounter tables and well designed monster entries and massaged into something meaningful by the DMs powers of imagination.
The key to doing it well is having a good sandbox, so that you can interpret a random event or encounter in the context of the world around it. Really extensive and well documented random encounter tables are a plus.
Let me start from the beginning.
1) I create some meta-plot for the area. This is the 'important event' going on or the 'important event' all other events are leading up to. The 'Powers that Be' in the area are bending everything toward this important event and ultimately you intend to involve the PC's in the 'important event'. However, you don't know exactly at this stage how you'll involve them or even which side the PC's will take.
2) I make a big map.
3) I create the big 'Powers that Be' for the area (probably without stats at this stage) and put there lairs/strongholds/cities on the map (often without maps at this stage). These are the major NPC actors.
4) I create a wandering encounter table for the major map divisions which is sufficiently detailed that the results will be surprising at times and predictable at others.
5) I give the players some initial reason to want to move across the map.
Now, as we start play, we might get some wandering encounter result. I look at the result and think, "Is it impossible that this is true?" If its not impossible, then it must be some new discovery and I try to make it work.
For example, lets say I get a result of 'Orcs' and I know that orcs are encounted in their lairs 10% of the time. Then I roll that and I discover that its not just orcs that are encountered, but an orc lair. Viola, I have new map feature and a new minor player in the area - this orc tribe I previously new nothing about. Who are they allied with? What do they want? Are they in on the plot, or just useful tools or annoying foils? What resources do they already control, and what do they do for a living? Are they farmers, bandits, mercenaries, slavers, miners, or some of all of the above? Answer this in accordance with what you already know about your invented area and what inspires you. And after this, any further orc results tend to imply encounters with the orcs of that tribe I invented. Or conversely, if no lair was encountered the first time, then it likely true that there is a lair somewhere around here and I either need to place it or be on the lookout for a good place to place it.
Ideally, when I roll 'orcs' encounters, its not just with 'orcs'. That band of orcs could be mercenaries, bandits, merchants, slavers, farmers, hunters, ranchers, refugees, pilgrims, and so forth. They may or may not be interested in the PC's, and may or may not be hostile. They have an agenda and its not just 'get killed by PC's'. How the PC's interact with the group sets the stage for future interactions. NPC's created here may disappear, or may become reoccuring personages. I roll orcs the next time, maybe I decide its the same band of orcs, or at least the same NPC.
Let's say I roll a result of something wierd, like a water monster in a desert. Well, this implies the existance of an oasis and if ok with that, well, I just put some other new feature on the map. Now, I've also just created story. All the intelligent monsters in the vicinity would like to use the oasis, but they can't, because of this water monster.
Similarly, every wandering encounter is effectively authority to create a small terrain feature and even a new map subdivision if you want. You can create bridges, roads, stream, caves, abandoned mines, ruined buildings, etc. Just because your 6 mile wide hex says 'Forest' on it, doesn't mean that there aren't stands of ancient hardwood, pine thickets, gullies with steams in them, outcroppings of rock, small hills, rolling ridges, fairy woods, haunted sections, abandoned homesteads, glens and meadows, small ponds, clear cuts by loggers, burned out areas from forest fires, and whatever else you can imagine. As you need more detail, add it.
Where I think that this gets tricky is pacing. This sort of hexcrawling can take up alot of time with what is in essence 'meaningless' events. It does give the feeling of really living in the world, but merely living in the world is not necessarily a really exciting or fulfulling thing to do. You might have noted that I answered in detail how you create exploration areas, but not necessarily how you create motivation and meaning to that exploration. Back in the day, when I was first RPing (and 12 or 14) that question didn't concern me too much. Killing things and taking thier stuff, and occasionally not killing something and deciding to befriend it, was enough. In previous hexcrawl campaigns I did, I always felt that while I had lots of awesome planned, I wasn't doing a good enough job showing the players the awesome admidst the mundanity of the world. I was waiting for the story to grow naturally rather than hitting the players with story from the first page, and just as it would be in a novel, that's not the best way to go about it. You want the awesome to be on page 1 if it is anywhere, then after you can do your breathing life into the world.
So I'm structuring this campaign different than my previous ones. We're going to go with awesome first, then later bring the sandbox, rather than sandbox first and later bring the awesome.