Well, for some characters it justs fits that they would be called a certain name, for me at least. But for the rest, sometimes I pick something that's to do with their personality, or in one case the role they have in the story. A have a character who plots to betray one of her friends and I named her Arnica, which is a flower that looks like a daisy but, if eaten, can make you sick.
When making up a name I just roll things around in my mouth and see what comes out. If it's nice, and I like it, I'll use it. I also twist spellings around, e.g. Karyn, Jordyn.
Character names don't really have to be un-common, though - I'd rather read a story with a Jane than a Jaelakyraen, get it?