I'm leveling a warrior right now also.
Prot is pretty nice since tank queues are literally instant with random dungeons, but I dunno, I'm not really a fan of tanking personally.
I want to go fury because Titan's Grip with dual BoA arcanite reapers seems like fun, but I keep reading that it's actually not that great until end-game because of a lack of hit.
Prot is also stupidly easy to level if you do normal leveling (hell, all tank specs are easy to level) because all you need to do is aggro everything in a huge radius and burn everything down pretty quickly (especially with BoAs). Makes quests a breeze, really, and you're an unkillable death machine.
The thing though is that Tanks are in high demand pre 60. When you start doing BC dungeons, it's always Healers that are missing. ALWAYS. I've had 5-10 minute queues with my Brewmaster around level 60 for some reason, and if I switch to Mistweaver I get insta-queues.
What's also funny now is that I'm going through the BC dungeons because, well, I'm 66, but it's a pain because you don't get that much XP out of them. I did 4 levels just herbing, which was kinda cool, so now it'll be a breeze to get to 68 and head to Northrend.