I’ve made toons purely because I thought up a good name, these are my stratagies, but please help others with yours!
In-game Theme:
There are thousands of NPC’s and named locations that work great for character names, sites like wowhead.com have complete listing of NPC’s and Zones. Some variation will be required, but usually you can find some inspiration.
Example:
-Killsarkoth named after one of the bosses in the Troll/Orc starting area (Sarkoth the scorpid)
-Murlocchow, fairly obvious where that one comes from
Your Favourite…:
This can be food, animal, TV series, movie, book, town, you name it!
Example:
-Angua, a character from my favourite Author; Terry Prattchet.
Phrases:
Here is where you’ll have to get really creative, find a short phrase or expression and try to make it fit.
Example:
-Abitsquirrly, this one was easy, all I had to do was drop an E, and voila Abi T. Squirrly gnome extraordinaire!
-Eatandbmerry, from the phrase “eat, drink and be merry” I simply dropped “drink” and an E, a perfect name for an Undead.
-Necesaryevil, another easy one, I just dropped the extra S.
Descriptive Words:
Self explanatory, like the phrases, you just pick a word that describes your character, or the image you want to project.
Example:
-Erradikate, I had to play around a little bit, but it still looks good, too bad I went Resto
-Saviour, going to be a Worgen Druid when Cata hits, atm he’s a Resto Shammy gathering dust.
Mythology:
Mythology is a great resource for name ideas, don’t just look at the heroes, sometimes the side characters have great names too.
Example:
-Lycia; it is a town in the myth of the Chimera, and is actually a compromise for me, the Chimera is my favourite mythological creature, but the name is always taken.
Languages:
Along the same lines as Descriptive Words, but with more flexibility, if the name you want in one language is already taken you can search for it in another! Translator sites are common enough; I believe Google has a version.
Example:
-Ossa; it means bones in Latin, a pretty name for a pretty corpse
Humor:
Be careful with this one, you don’t want to go too silly; otherwise you might not get taken seriously.
Example:
-Ewedied, if I PVP’d I’d use this name, I think it’s great, but it’s wasted on me
-Cheekydevil, IMO a great warlock name.
-Cellardwellr, had to drop the E, but it still works.
Advertising:
I don’t sell my services often, but it would make things easier if you could just look at some ones name and know if they’re the sort who openly sell, and can be approached.
Example:
-I really like the idea of using lnc, the small L in the Warcraft font looks like a capital I, so something like Rubieslnc for a Jewelcrafter or Plustwolnc (as in +2 <insert stat here>, I felt I had to explain that one), Essencelnc/Enchanterlnc, etc
-Putting your preferred role in your name; Ihealforgold, etc, also, it’s pretty easy to tack DPS on to a short name.
Name Themes:
Basically this is for when you don’t want any confusion as to who you are. One of my Guild Leaders does this; almost all of his toons have Bruce in them that way you always know it’s him on.
Hunter and Pet Themes:
Most of my Hunters go by this strategy, first browse your options on Petopia (where else would you go?
) and find a pet/pet family/look etc., that interests you, and come up with something which goes well with that scheme. Also, is there a name you really, really want, but it's taken? Pets are also a way to get the name you want, just give your Hunter a name which compliments the name of your future pet.Example:
-Shimmerwing is my all Moths Hunter, she even has moth vanity pets.
-Rabidpenguin is birds and Polar Bears
-Meadowhawk is all about the birds!
-Killsarkoth (mentioned earlier) has a Scorpid; SonofSarkoth
-Datcord; I wanted the name Discord, of course it’s “Unavailable” so I made the Troll Hunter Datcord (sounds vaguely Troll’ish) and named my pet Discord.
Already used it to check to see if I can use a name (I want my boyfriend to make a "mate" for one of my current toons, so now I know it's probably available.) 
