Protection is awesome for leveling. You get a lot of defensive abilities and you still rock nice DPS all the way up to end-game Cataclysm.
Pick up a two-handed whatever and go do quests until you hit level 10. Get a shield and a one-handed weapon. You get an ability called Shield Slam at level 10 when you choose Protection. This is your new best friend. It hits like a truck AND it dispels a magic effect.
With your first two talent points (level 10 and 11) you should pick up Blood and Thunder. This really boosts your AOE damage to ridiculous levels. After that, start fleshing out the Protection talent tree with talents you think will increase your DPS and survivability. At level 29 you'll be able to get Warbringer, which makes Charge usable in combat. That's when the fun begins. Being able to charge while in combat gives you a lot of mobility, which is downright sexy in PvP.
As for stats, go with gear that has strength and stamina on it. Once gear with secondary stats pop up, begin stacking hit rating, crit rating and expertise rating. You don't need mastery rating until level 80 at the earliest. You may want to get some gear with dodge and parry on it once you hit Northrend as the jump in damage taken between Outland and Northrend is huge.
Protection Warrior is one of my favorite classes simply because it's so much fun, both in PvE and PvP. Battlegrounds feel like playgrounds with all the tricks you get. Once you hit level 85, you'll have four charge abilities available.
It's hilarious when you use these four abilities a lot. And while you can't dish out a whole lot of damage in PvP now (due to lack of Vengeance), you can sure as hell take a beating while being a royal pain in the ass. I went into a Battleground at level 85 in my PvE gear (had no PvP gear, not even a trinket) and it was a blast. I died a lot, but I could hold off four PvP geared players for 30+ seconds, which gave my team mates some valuable time to cap flags, or resurrect and come to my rescue.
And don't underestimate Shield Slam. That thing hurts. I got in quite a few kills because of it.
____________________________Please "talk up" if your comprehension white-shifts. I will use simple-happy language-words to help you understand.