Here's what worked for me well while leveling as a warrior.
Level 15:
Talent Calculator - World of Warcraft - You want to begin teching down the Arms tree, with a two hander. Parry is good for survivability, and you charge every mob you fight.
Level 20:
Talent Calculator - World of Warcraft - At this point, you can take either imp rend or imp. Thunder clap. Ignore anger management, fights never last long enough for it to generate a large amount of rage, and it doesn't slow decay out of combat anymore.
Level 25:
Talent Calculator - World of Warcraft - This seems obvious.
Level 30:
Talent Calculator - World of Warcraft - The point in deathwish could be in a weapon specialization or impale.
Level 35:
Talent Calculator - World of Warcraft - I like axes, but if you like swords or maces, go with that. I don't recommend maces though, as it doesn't add damage and the stun is not controllable.
Level 40:
Talent Calculator - World of Warcraft - RAWR Mortal Strike. Also, Imp. Disciplines, because warriors are terrible at fighting elites or groups of mobs at once. Retaliation/Recklessness makes certain quests very easy.
Level 45:
Talent Calculator - World of Warcraft - Because critting is good, and the other high level arms talents aren't great for leveling, much better in PvP or group play.
Level 50:
Talent Calculator - World of Warcraft - Tactical Mastery is useful for any number of reasons, but mostly it's so you can disarm a melee opponent easily. Imp. Bloodrage gives you more rage, and lets you keep rage longer out of combat. Very useful.
Level 55:
Talent Calculator - World of Warcraft - Most mobs do physical damage. This makes you take less of it. Less damage = less time eating/bandaging = faster xp.
Level 60:
Talent Calculator - World of Warcraft - I like Last Stand, it's great when you're in a close fight. Warriors get in those a lot if you're fighting a higher level mob. If it could go either way and you don't want to die, Last Stand. Defiance is also very useful, for the expertise alone. It also helps with tanking, which you'll be asked to do a lot. And you might as well finish off imp. Disciplines while you're at it.
At this point, you can go many different directions, more Arms/fury for better DPS ability, or more prot so you can tank all those outlands instances better.