One day I will play a game with only palindrome-named characters.
Zez Sarabaras Ordro
Ksisk Lol Rabar
Sos Abba
Yalinanilay
Heinikodeiedokinieh
All Killik hive names are palindromes. I thought that was a pretty cool naming scheme for a species.
As for how I name characters, I like to find examples of that character's species/race and do something similar. For my Rattataki bounty hunter in The Old Republic, I looked up Kaliyo (a rattataki companion of the Agent) and found it was an Indian name. So, I looked through Indian names until I found one that I liked.
My smuggler in our group's long-running RCR/Saga edition campaign is Jacen Hallis. The name Jacen has an obvious origin, but Hallis is a homonym for Halas, a city in Everquest, which we were all playing heavily at the time we started. Jacen's companion and later wife, a force-sensitive twi'lek (and also my PC; I play two characters in the campaign) is Ruminara Ven. I liked the name Rumi after hearing it in a number of anime, and I added some stuff to "fantasy" it up. Then I found a good clan name to give her: Ven, which is the clan name of Nawara Ven, a character in the X-Wing books.
I find names any number of ways. And I keep a list of names I find interesting. Sometimes, I think up names and characters simultaneously, just waiting for the proper campaign in which to use them. Sometimes I make them as NPCs and let my players meet them.
Edited by Lickintoad