I ususally go look at a name etymology website and choose something for the character based on the meaning, and then I'll maybe change it slightly to make it sound more like a fantasy name, if I need to. For instance, I chose my protagonist's name of Micah because it's a bit androgynous and it means "in the manner of god" which relates to a theme I have running through the books.
I don't like having really "out there" names, though--no characters called Mh'heeninala'ani here. Some other examples of names I use in my quasi-steampunk novel are: Aenea, Drystan, Elena, Ceren, Esti, Gytha, Bottle (it's a nickname), etc. For my characters from other lands I choose names from whatever culture I'm somewhat basing them on: Zeki, Kato, Zuri, Dani, etc. Oviously I like two syllable names, hmm. I should mix that up a bit more.