I did naming characters, so this seemed the logical next step.
When it comes to setting a story, I tend to be vague. My two 'real world' projects are both vague in their setting regarding anything more than country. The only project I'd consider naming the setting in details is the much mused-about Roman project, since the settings would be relevant to the plot. When place isn't relevant to plot, especially in any kind of 'real world' setting, I avoid it.
But in Grenhelm, well, that's fantasy. Places need naming. And my attitude to it is much the same as to character names: they have to be realistic (apart from those I made up when I was thirteen and can't bring myself to rename!). While the individual countries have made up fantasy names, the towns and villages have names that wouldn't look odd on a map of England. Well, Southern England.
There are two types of place name: descriptive, and enticing. It's the difference between Iceland and Greenland. You don't tend to find many enticing place names in 'old' countries; they're something associated with exploration and settlement. Most of Europe was settled before it was officially named, so the names tend to be descriptive, which is what I'll be focusing on.
In Britain, there are multiple languags to draw on to compose these names, and in a fantasy world, the same can apply. However, if, in your protagonist's country they speak what is basically English (or the language is 'translated' into English), and other influcing languages aren't immediately recognisable as French or German or Latin or Old Norse, then you need to be careful about using those languages to name places (it's that etymology thing again). You need to stick to recognisable dialectal variations on English words, or you need to use words that your readers will recognise as part of your invented languages.
Since I don't have any invented languages, I've been naming places in a noticeably English way. Famous people, names of local landmarks (usually rivers), combinations of landmarks, type of settlement and geographical positions. There's a lot of variation on spellings, though I've only thrown it about in a few of them.
Prefixes tend to be geographical, so you've got the following:
e- we- su- so- no- nu- nor- etc
You can also preface a place name with North, South, East and West, obviously, as well as other descriptors such as Greater, Lesser, Small, Under, and so on. These usually come into play when there are multiple places with the same name, usually because they're in the same region (so you can have a Greater and Lesser Hillmouth, for example)
Suffixes tend to be geographical landmarks, though it also includes other obvious descriptors, such as the type of settlement (which may no longer be accurate by the time the story begins). This is not an exhasutive list:
-ford -bridge -mouth -port : all river related
-hill -lee/ley/ly/leigh -vale -head -stone -down -cliff : hilly/mountainous regions
-green -field -broad -flat : flat or lowlying areas
-bush -wood -marsh/arsh/ersh/mersh -heath : local ecology
-ton -ville -ham : type of settlement
-bury/bry -home/house : people related
Again, sometimes you find suffixes as separate words; these are usually geographical, and clarify position further, for example, Hillmouth Green. These suffixes are usually recognisable whole words in English (so you wouldn't have Hillmouth Ville, for example).
I'd like to point out that Hillmouth appears to be a nonsense name, since it's fairly improbable that a river would be called the Hill (also, Ville is a fairly french looking word; it represents village, which is more English, but it's a suffix to use carefully). However, our river that this village is at the mouth of might not have been called the Hill, back when our village was named. It might have been the Ill, or the Hile, or something like that. The difference between separate and conjoined prefixes and suffixes is lazy speaking. When creating a place name, it's best to come up with something obvious, and then repeat it until you start mumbling, and see how it sounds. Syllables just fall out (to take a real example: the Guilded Ford is now Guildford, where Ford Prefect claims to be from, and that central d is almost never pronounced).
Pronunciation is tricky; only the writer knows what is intended, and attempts to make it obvious can just baffle people who grew up with a different accent to yourself. My advice is not to bother with anything other than the straight forward.
To run through some place names in Greenhelm (which is the Green 'Helmet' of the island), I've names a couple of rivers the Song and the Let. So there's almost certainly Songmouth and Letmouth, and probably places like Songford, Letbridge, Songmarsh, Letleigh, and Songton, and minor changes (sometimes just in pronunciation) to give Songreen, Sonersh, Lefford and Letham. Trust is rumoured to be buried in a certain area, so the town there is Trusbury. In the empire, you'd expect to find the occasional Kingbry and Queenham. There might be a Wonmarsh and Tomarsh on the border - one side of the marsh and t'other side. Oakley and Yevale would be a valleys of oaks and yews respectively, and Redford would be a crossing through an iron-filled river.
It's so... easy. Of course, some of these names probably already exist, somewhere in the British Isles, in some form. Naming places like this can help solidify geography without a ton of maps (though it's worth mapping a place for your own sake, to make sure you don't end up with Treemouth in the middle of the mountains, for example) and can also give names to fictional places in real world settings. If you want latin or french or spanish names, when you just need to pick some appropriate components and run them through a dictionary; the nice thing about place names is that they don't need to be grammatically correct. The same goes for invented languages, or course.
If you're still absolutely, one hundred percent stuck (or you don't want to name somewhere in England!) then Paperback Writer has a good list of name generators. They're good fun to play with, especially the inn names.
Naming places is something personal, but like naming characters, I think there has to be a certain consistency to it. If every single place as a completely different made up name, they're going to be hard to remember, and they're going to make me wonder why people in this universe are somehow dramatically different to every other culture I've encountered in our universe. If the made up names have some consistency, then I'll start to think they were named by people speaking a slightly different language (York, for example, comes from the Norse name Jorvik thanks to the invading Vikings, and thus would look out of place amongst the Milfords and Brightons of the Anglo-Saxon South East). If elements of that language are still lurking about, even better.
Places were described before they were named, so people could find them. This will be true of anything set in Europe or Asia, and anywhere in Africa, Australasia or America that still has it's native name. It ought to be true of almost every fantasy novel I've ever read, though it hasn't always been, which is a shame.