Suprised none of you mentioned rogues. I'd say that's the most popular class. If you use cosmos (
www.cosmosui.org ), a User Interface Mod for WoW which allows you a lot more flexibility and more bars to put hotkeys on, it has a server census ability which tells you how many of what class are on the servers. Shamans are the highest on the server I play horde as, and rogues are the highest on the server I play Alliance as, with palladins close second.
I've got a bunch of mid-midhigh level chars:
Archimonde(which is the only server i play on anymore):
Zerathis-Level 43 Night Elf Hunter
Zerathuel-Level 23 Human Mage
Zerathan(just made 2 hours ago)-Level 8 Human Rogue
Shattered Hand(don't play on it anymore. Alliance outnumbered the Horde way too much)
Zerathis-Level 38 Tauren Warrior
Zerathuel-Level 35 Undead Priest
Zerathan-Level 24 Troll Rogue
Keep in mind, I've been playing since release... so...heh. If only I stuck with one character...
Here's a video of what Rogues can do to people:
http://www.wowreview.com.nyud.net:8090/Subtlety.avi