The very first thing I start with is laying out races and cultures, along with history. I then decide what deities these cultures need and how they interact with each other. Then they need to be placed on a map, which may lead to changes to your earlier steps as you begin to see how the physical and political boundaries line up. From that point I just have a very vague sense of the world, but enough to inform my players of the general feel of the world. I then place more specific features as the campaign progresses and through interaction with player wishes and backgrounds.
As an example I'll use the world I'm currently working on: Mythros.
The core concept of the world is that it's a time long ago when humans first rose to dominance. There is only one civilized land and from it sprung all future cultures, they are the progenitors. Every human city is a mix of Greek and some other culture; there are pure Greeks, Greeks-Norse, Greeks-Egyptians, etc. Each nonhuman race reacts differently to the rise of man. Elves react violently and are resentful, humans and elves have constant hostile flare-ups. Dwarves are on the other side of the spectrum, stoicly accepting their fate.
So how would the religion of this world look? I decided to go with the primary faith being worship of the one true god to give a unity to all the human cultures. This god is the same god that will eventually be rediscovered by the Abrahamic faiths. This god is served by lesser divinities that take the place of lesser deities in other campaigns. Zeus, Odin, Ra, and many other divinities that will someday be worshipped as the lords of their own pantheons are among these servants; as is Satan and others who will eventually fall from grace.
Then I thought about the geography of this land. I decided to place elves in the far west, occupying the last of their forest refuges. Dwarves occupy the northern mountains. Most of the other lands are various human cultures all living far closer together on a relatively small land (a very large island really) that is fated to be swallowed by the ocean, scattering it's human inhabitants to the far corners of the world (humans are the only race to master seamanship). I see no need to change any of my earlier assumptions due to this.
I now have a very vague land, but enough flavor to allow players to understand the world around them. If a player wants specific events or locations to be part of their character's background I'll make every effort to include it. I will slowly add details as the players explore the world around them. Eventually it will evolve into a detailed and vibrant world.