There seems to be a lot of prejudice against world maps these days, although I'm not really sure why. I like being able to get a bird's eye view of the world I'm wandering around in, personally. It makes it easier for me to understand where things are in relation to each other than having a bunch of interconnected areas.
Anyway, to address your question: what I do is, I start with the locations that I know are going to exist (y'know: starting town, bad guy's fortress, first dungeon, stuff like that) and I place them down approximately as far away from each other as I think they should be. Then I start filling in details around them. Is the villainous castle up on a mountain? Okay, so there's a mountain range to draw in. Towns need water, so is there a river by the player's hometown? Let's draw in the river, then. How am I going to "funnel" the player toward the correct path? Maybe I'll draw in a forest to block them off.
Once I've exhausted my initial ideas for the map, I start the story rolling and let it walk through the established locations. Almost inevitably, by the time I reach the end of the locations I've already created, my mind has an idea of where the player ought to go next: a volcano? A plateau? An island? So I just add that in and continue the story. By taking regular looks at how the map is forming and adding in things that look like they OUGHT to be there (i.e. why does this lush plain not have any people settled on it? Why does this important bottleneck not have an Imperial fortress to act as a lookout?) the map fills up quickly. Throw in some bonus areas, clean up your lines, and put a bit of polish on it, and your world map is good to go.
