My preferred method is to just pick a word that sounds amusing at the time and go with it. Yeah, I pretty much always ignore the lore. Lemony and Hemoglobin were my two main WoW characters back when I played. I also prefer to get the very shortest names possible in MMOs, which led to Ibu and Tex for my tauren characters. I thought the latter was surprisingly fitting for a walking cow. Of course, my other method is to just look around the room and see what catches my eye. This led to a LOTRO character named Eula, which I thought had a surprisingly good ring to it.
If those methods fail, I’ll boot up my preferred random name generator and keep trying till I get something I like.
My hero is always Smedley Beerfart. Every other character has clues about what he is, A dwarf fighter will be Roloff . A mage will have some magical connection. Houdini for instance. A healer will be named Sweitzer or DeBakey. I don’t want to think of what he is before I move him.
In City of Heroes I came up with cool superhero names and then built the character around the name rather than vice-versa. Schtick (Ice/FF Controller; “Being a Tank is my Schtick!”), Ramification (a sheep themed Stone/Mace tank), Black Hat (a cowboy themed Fire/Fire dominator), and the Outsourcer (a Soldier Mastermind) were some of the more memorable ones.
When I’m playing on my own, I either randomize or just hit keys. I don’t really need anything special there.