I usually start with what I need the map to do. That is, I have some idea of what story I want to tell, how many nations and what size of landmass I need to tell it. Then I sketch out a rough relationship map of all the geopolitical factions and their issues.

Then I sketch the coastal outline, draw rough political borders, and drop in topographic elements where they make sense for my story. I then look at it from a geologic perspective to make sure it doesn't violate any major rules and revise based on that assessment.

Then I scan the rough map and bring it into Photoshop to start on prettifying it.

That's my current process. It's been different in the past, and I'm sure it will be different again in the future.