Well, since I've started playing Oblivion recently, I give some examples of my thought process.
1. Made a female Nord Warrior. I wanted her to be fierce, but noble. Since she was blonde to match her race's description, she reminded me of Eowyn from The Lord of the Rings. She's my own personal Shield-Maiden. So, I named her Eowyn.
2. Female Imperial. Small, pale and intelligent. Named her Elora Danaan after the little Princess from Willow. This was more an emotional naming, rather than practical.
3. Female Wood Elf. She's a murdering thief and an eternal bad-ass. Couldn't think of a name that felt small and deadly like I wanted her to be, so I looked up villain names on Google. The name Ursula popped up. Like it, chose it.
This is my standard procedure. I decide who my character will be and go from there.