Hey there, I have leveled a warrior to 60 on a vanilla server (including my first play through on vanilla retail) 4 times, and I am currently leveling my 5th warrior right now. This is the spec I always go when leveling, and I think that it is by far the most efficient spec point for point when it comes to leveling and questing:
http://db.vanillagaming.org/?talent#LbGxbAio0zVVhVMI always argue that leveling Arms is better than leveling as Fury. From a gear perspective, it is much easier to continue to upgrade a single weapon as opposed to two, and if you can get someone to help you get Whirlwind Axe at level 30, you will be set and not replace it until the mid 40's.
For the first tier, immediately go for 3/3 Improved Rend. You should be immediately rending every single target that you attack at lower levels, especially below level 20 for the guaranteed damage. Next, I choose to put 2/3 points into Improved Heroic Strike over Deflection because 2% parry doesn't really do anything, while a reduced rage cost on one of your main abilities is beneficial when you are rage starved with a 2h weapon.
At the second tier, I will immediately go for 2/2 Improved Charge. Pretty self explanatory. The rest of the points go into 3/5 Tactical Mastery, which will not be very useful until level 30 when you get Berserker Stance, but is still much a better choice compared to placing 3 points into Improved Thunder Clap. I hardly use Thunder Clap at all when leveling.
At the third tier, immediately go 2/2 Improved Overpower. This is one of the best talents for an arms build, as 50% extra crit chance on top of your base crit with an Overpower can make any target that dodges your attacks easily chunkable and crittable. Afterwards, fill the last 3 points at this tier with 3/3 Deep Wounds. I always go for 2/2 Improved Overpower before 3/3 Deep wounds, because you really won't even crit much in your 20's without 2/2 Improved Overpower, therefore rendering Deep Wounds useless for 5 levels if you spec into it immediately.
At the fourth tier, go for 2/2 Impale and then 3/3 Two-Handed Weapon Specialization. Impale is amazing as it makes your crits increase from 100% bonus damage to 120% bonus damage.
At this point, your talent tree should look like this at level 29:
http://db.vanillagaming.org/?talent#LbGhbIbOnce you are level 30, instantly spec into Sweeping Strikes, and get used to using this ability any time you attack more than one mob at a time, and make sure to combo this with Cleave. Once you get Whirlwind at level 36, that move will take priority, as you will be able to get another normal attack off, in addition to two hits from the ability itself, for rage generation, but if it is on cool down always use Cleave in it's place when Sweeping Strikes is active. When you use abilities like this when Sweeping Strikes is active, both hits proc Sweeping Strikes, so it is as if you are simultaneously hitting both targets twice at the same time, for a total of 4 hits, which can end up as massive damage if you also land a critical strike.
Next, I immediately put 5 points into Axe Specialization, as 5% crit is much better than the other specializations. Polearm Specialization has the same effect, but there are basically no good polearms for warriors, with the exception of something like
Ice Barbed Spear from AV, but you can only get that at level 51 at the very earliest, and it's not something you can easily obtain if you want to level efficiently. Also, the fact that it is in the next tier also affects this decision, as you would need to wait to place points into this instead.
However, this means
you must stick with two-handed axes for most of your play through to 60 unless you want to spend money respeccing for another weapon. This is not something that is bad by any means though, in my opinion, some of the best two-handed weapons for leveling are axes. And you will
always want to find a two-handed axe with the slowest speed possible, therefore granting the most top-end damage, and therefore maximizing the damage of your critical strikes. If you can get
Whirlwind Axe in your early 30's, this is by far the best two handed axe to use until level 43, in which case
Executioner's Cleaver can replace it if you can afford it. Executioner's Cleaver is an amazing weapon for this level, and I'd argue that it is even better than
Kang the Decapitator for two reasons. First, the 1% hit chance is absolutely amazing in your mid 40's, and the 23 strength turns into a decent amount of attack power, whereas Kang the Decapitator gives you no strength or hit chance, for a meager increase of about 6 dps and 10 damage on the top end. I won't even elaborate on the effectiveness of the proc, because the consistent benefits of +23 strength and 1% hit certainly outweigh the proc and slightly higher top end of Kang the Decapitator when leveling. I will use Executioner's Cleaver from level 43 until I respec protection in my late 50's, and I always try to obtain it at or before this level, even if it costs me a bit of gold.
Next, immediately finish putting points into Tactical Mastery for 5/5, as you will be (or should be) stance dancing from Arms Stance to Beserker Stance regularly in order to gain the rage from Charge, and then still benefit from the extra 3% crit of Beserker Stance, and keeping the extra rage is great when you need to stance dance for an Overpower when an enemy dodges. After this, finish putting points into 5/5 Two-Handed Weapon Specialization. You will be level 39 at this point, and when you hit 40, it is obvious that you should put your final point in the Arms tree into Mortal Strike.
Mortal Strike an amazing move despite a rage cost of 30, because it also allows you to get an additional normal attack off in addition to this damage, instead of your auto-attack being consumed by Heroic Strike. Personally, the only time that I even use Heroic Strike after level 40 is when I have excess rage and when Mortal Strike and Whirlwind are both on cool down, AND when I am only fighting a single mob, which is very rare.
At this point (level 40), your talent tree should look like this:
http://db.vanillagaming.org/?talent#LbGxbAio0zNext, immediately put points into 5/5 Cuelty for another 5% bonus crit, on top of the 5% crit you get from Axe Specialization. Booming Shout is not even close to being as good as 5% crit.
Now you are level 45! Put the next 5 points into Unbridled Wrath.
At this point, there can be many alterations as to how you want to place your final 10 points from level 51-60,
but I will usually go straight into 3/3 Improved Cleave for even more damage with the Sweeping Strikes and Cleave combo, and then dump the next 5 points into 5/5 Improved Battle Shout. And then your final two into Improved Execute for 2/2. To be honest, I usually respec Protection around level 58, so I usually don't even place these last few points, but it's just my personal suggestion if you are going to quest until level 60.
On a side note, I dislike talents like Blood Craze and Enrage for leveling, because mobs that are the same level as you only have a 5% chance to crit you and even activate these talents, and I think the bonus attack power and extra cleave damage is more valuable, especially when you are fighting tough mobs in your mid 50's.
Please post if you have any questions, and I welcome any criticism of my spec choices.