Toponomy, or How to Name Places!

[Diamond]

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.

I do that as well. Just a simple lexicon, just enough to get me going. Then, as the map progresses and I find myself in need of new words, I add 'em in, making sure to check with consistency and 'feel' with the original group.

For maps which are based on real-world cultures or nations, like France or Italy, I've found a couple of random name-generators which are very useful:

http://direpress.bin.sh/tools/name.html

http://www.squid.org/rpg-random-generator

http://nine.frenchboys.net/

I'm sure these are very widely known amongst this community, but hey, I like 'em.