I usually start with the story, much like Diamond mentioned above. I usually start with races,culture, history (how was the world created). From that part I try to make out some sketches of the world, landmass, climate etc. I usually try to make my worlds as realistic as possible, but without to much calculation. I don't really care about tectonic plates and stuff like that. But I try to get rivers right and I try to place terrain in places that look natural. When I'm done with the actual map, continents and oceans, I try to find good spots where civilization might have started out. I then place in cities and build out from that, adding countries etc.

In the end I hopefully have a map that looks quite convincing