I get the basic premise down, without direction from the start it can be difficult to go back later and make all the pieces fit. If you get your beginning and your end down first, it is easy o thread the content between the two, and you have a much better "jigsaw" by the end.
After that comes sketching the worldmap. I don't usually do names except as a sort of reminder, usually based on landmarks or their correlation to real-world locations if they are base on a physical region, as the canon games are (I did the Nile Delta once). I leave actual final-draft names for when I get to actually mapping them, at which point I do whatever seems to fit.
If there are Fakemon, designing them's the next step. Only then does the actual work begin, usually with implementing any majour mechanical hacks I know how to do that I want in the hack, then doing the rest as I go along.