Toponomy, or How to Name Places!

[Gidde]

I like to make a mini-language, just a few hundred words, making sure you have words for things like natural features, colors, Gods, common adjectives, etc. The you can convert your English names to more exotic-sounding names, but you have a pattern and a consistency you wouldn't have if you just made up random names.
For maximum consistency, you'd have to have some Religion, Culture, and History developed before you name most of your places.
Probably too much work for a quick map, but for a world you plan to spend a lot of time on, I couldn't imagine doing it any other way.

Holly Lisle did a great (drm-free e-)book on a simple way of creating a realistic language that if you're into spending a few dollars on, I found really useful. It's a great addition to my (rapidly expanding) worldbuilding library.