In my early days of gaming creating maps was one of the greatest joys - next to making and drawing characters, and arguing over rules interpretations (the High Gygaxian dialect didn't exactly help settle any issues). Learning how to create fantasy names for places was a natural result of the many world maps made back then.
I would create multiple lists of syllables, number them, then roll dice. Getting results like: dol + mar + anth + uz = Dolmaranthuz (a name still used in my world of Dungeoneer). This tedious method has been replaced by great fantasy word generators online like this. So nowadays I'll just generate a couple of lists, edit them down to my favorites and get to the fun of writing up descriptions and illustrating characters, places, and things.
This isn't a completely random method though. I do try to get words that sound similar and assign them to the same race/nation/place/thing for some semblance of believability. Also it helps to use real world cultures as a guide, if something sounds Nordic for example I might give it Viking or Norse properties.
For the world of Lavivrus though I'd do something special. Since this is an homage to Greyhawk and Blackmoor, and those early days of yore, I thought it best to generate place names using anagrams of names of those who helped define the hobby. I went through several of my old books and wrote down many of the names of creators and collaborators. Then took those names and pulled out letters & syllables, and twisted them around into some interesting sounding fantasy names. Yes, the tried and true old school method! See how many of the names you can recognize in this list.
Note: this version of the map has been revised from the last one I posted. I wasn't happy with how garish the colors had turned out on the textured map, so I did a polishing pass on the colors and textures before placing these names.
Next: nations and cultures