Once I have a pretty good idea of the story I want to tell, I start building the world. And by "build the world," I really mean "fill a 3-ring binder with a bunch of notes, loosely sorted by category."
I usually start with the mythology first: the story of how the world was formed, the gods and heroes and legends that were associated with that story. Sometimes I'll make multiple versions, too. If the story is about the struggle of druids against human expansion, for example, I would write 2 different mythologies: the mythos according to humanity, and the mythos according to the druids. Yeah, it's overkill but it comes in handy later, when I'm having to ad-lib a Legend Lore.
Then I shift gears to geology. I start drawing maps, imagining how the islands and mountains formed and how they might have changed over time. (I have a geology background and I love drawing maps, so this is my favorite part.) Rivers and mountains and deserts and forests...this is the best part of world-building for me. Once I have a rough map I'll add the hometown(s) of the characters and work outward, adding only the details that are needed for the story I'm telling. The entire story of "Treasure Island" takes place on a single boat and a single island...there was no need for Robert Louis Stevenson to map the entire ocean.
Then I write the history, starting with a timeline: on the far right is the present day, and on the far left is the oldest recorded history. Then I fill in the gaps with only the stuff that will be relevant to the story I plan to tell. Nothing too detailed here, just a dozen or so key events described in a paragraph or two. The players will fill in the gaps later when they add their character backstories and family histories and so forth...best to keep it flexible.
And lastly, I create the random encounter tables. I cherry-pick the races and monsters that I want to have in the story, and ignore the rest. Sprinkle in a few interesting NPCs, and I'm ready to go.
The whole thing changes and evolves over time as the story progresses. I add, change, and remove pages, new NPCs arrive and old ones leave, players roll up new characters...I think my game runs smoother that way.