I make up names that seem appropriate for the game. I often spend a long time coming up with them. Examples:
Asheron's Call: Cirrus Ganderheight, Kendall Stormbright
Fallout 3: Cobb (no first name, just Cobb)
Champions Online: Jupiter Jones, Nikki Nitro, Cygnus Alpha
Borderlands: Frankenfragger (Brick), Dirt Nap (Roland)
Sometimes the name dictates the appearance and mannerisms, sometimes the other way around. I thought Jupiter Jones sounded cool, but had no idea what he would be. Eventually he looked sort of like Iron Man crossed with a clunky old diving suit. With the extra-wide body structure, and huge, rounded red armor with white/yellow trim, he looked a little like Jupiter. My Fallout character, on the other hand, I had already decided to be a mercenary butt-head. I named him Cobb after Jayne.
Sometimes the characters share families -- Kendall was only one of three Stormbright siblings I had in AC, the others being Kirk and Kylie. I used the last name Weatherbie in half a dozen tabletop games, with elaborate explanations for how characters from Shadowrun, Rifts, and Call of Cthulhu were related.