One important thing to consider is what kind of "feel" you want a particular area to have. For example, I wanted one area of my map to have a persian feel, so I started looking at Persia in an Atlas for ideas. Then I had my husband read the names of cities and areas to me and wrote down what they sounded like (which was generally much different from how they were actually spelled) and then I tweaked them here and there to make sure they were really different from the real names.
Another great resource is NameMage:
http://www.mapmage.com/namemage.htm
The files it uses can be modified, so you can get names with a particular flavor.
Finally, try using online translators. I had a mountain that was kind of brain-shaped, so I went to a English-Russian translation site. Russian for brain is "Mozya", which I thought sounded cool, so it's "Mozya Mountain".
Good luck!
-Janice
aka Sparkle!