When I created my D+D world, I started with a large piece of paper (the old flip charts size, if anyone here is old enough to remember those), and drew a quick line sketch of continent and ocean areas. Then I added a lot of islands, a couple of mountain ranges, and a few rivers. That's all I started with.

Then I started writing lore, just making up "gossip" tidbits, a sentence or two each, throwing in names of people, places, and items, some history and some legend and some current events. (Example: "Percy the Doomed has reasoned that it may not have been the Ill-Starred Prince who was slain, but instead, his riddlemaster, due to some mistake by the demoness. The black bard of Quoob believes that the Hermit of the Fen is actually the Ill-Starred Prince, waiting for some unknown event to determine if his powers still work in this age, and if this comes to pass, he will one day come to power anew.")

I didn't know who Percy was or the Ill-Starred Prince, or the black bard of Quoob, or even where/what Quoob was, or the Fen, or what powers might be referred to. I just made up a lot of lore.

Then I started writing a single starting adventure module. From then on, I fleshed out the world and the map as I wrote adventures. I had a lot of ideas from the Lore to draw on, and I let the players tell me what they wanted to do.

(Example: The players wanted to visit the black bard of Quoob). At that point I decided that Quoob was one of the islands that contained a Great Market that was a crossroads in the ocean for moving goods around, and the Black Bard was a somewhat legendary living hero who had disappeared 20 years ago (and thus needed to be found by the players). That was when I drew the map of the island of Quoob and the town Quoob and the Great Market itself.

So what HBrown describes worked very well for me .... start with a minimum map, some ideas not yet fleshed out, a starting area, and let the players grow the story and you grow the map as needed. As they decide where they want to go next, I add detail to the map. The many islands start described in ways such as "an isle of low hills covered in bloodthorn", leaving me freedom to turn that island into whatever I want later.