I am often a little surprised at how often leveling guides and leveling advice is requested by readers. It's easy for those of us working on raids to forget what it's like for the new player, just starting out of Silvermoon or Mulgore for the first time. With the changes to the 1-to-60 game made with Cataclysm, it's never been easier to level. While Mists of Pandaria is bringing a whole new talent system, the 1-to-60 game is most likely not going to see another revamp, so we'll go forward assuming that getting to max level will take the same path. In order to discuss it, I went and rolled yet another warrior. It's for science, people.
For people rolling a new warrior, be it an alt or a new main, there is one thing I like to keep in mind: Know how you intend to level. Whether you're a new player or an old hand trying a warrior out, it's really helpful to know what you intend to do to get to max level. Each talent specialization is viable for questing and PvP (player vs. player), for instance, but if you're intending on tanking instances or flag running in WSG, protection is the clear winner. Arms may be the easiest to level, however, without the stress of tanking and fairly easy to gear up for.
Level 1 to 9 are the same for every warrior. We're going to assume you don't have heirlooms because a new player won't, but by all means, get them if you can. There's no heirloom shield, but you can get a variety of gear for other slots, for DPS, tanking or PvP.
Between levels 1 and 10, you're doing the same things no matter what you intend your future talent specialization to be. You start with Strike at level 1 and gain Charge at level 3. Strike will be your baseline attack, and Charge your opener whenever possible. Victory Rush at level 6 will save you quite a few times when you accidentally charge into more mobs than you can handle. If this happens to you, focus all damage on one mob so that Victory Rush will become useable so that you can heal yourself, then switch to the next target. At level 7, you'll gain Rend, a bleed attack. At level 9 you get Thunder Clap, an AoE attack that slows the attack speed of everyone it hits, making it very useful for those same Oops, I pulled too many! situations.
Basically, until level 30 or so when you gain Berserker Stance, all warriors will be in either Battle or Defensive, using roughly the same abilities listed above. Abilities like Cleave, Overpower, Execute and Cleave will fill out the suite as you level up, with Heroic Throw becoming your ranged attack (used mostly for pulling mobs to you when you don't charge to them). Battle Shout, gained at level 20, becomes key for all specs, as it generates rage and buffs your damage and critical strike rate by raising your strength and agility.
For more detail on attacks as you level to 60 (including making use of AoE abilities like Whirlwind), check out DPS Warrior 101 and Protection Warrior 101.
The stats you want and beginner specs
As you level, you'll be attracted to mail and then plate gear at 40. At level 50, whatever your talent spec is, you'll gain a Plate Specialization that will reward you with more strength or stamina, depending on if you're a tank or a damage-dealing DPS warrior. (Tanks get stamina.) This will keep you focused on your primary armor type. All warriors like strength. Tanking warriors like stamina, dodge and parry. (You won't get mastery on your gear until after level 80.) DPS warriors like hit, critical strike and expertise to cap, which really isn't terribly important at these levels. Just focus on strength, then crit, then hit. Fury likes hit more than arms, but you're unlikely to cap it while leveling anyway. If your arms warrior has more than 8% hit, he doesn't need anymore.
To give you an idea of potential talent specs at these levels, we have this arms spec, this fury spec, and this protection spec. You'll note that fury uses two one-handed weapons at these levels, because Titan's Grip isn't available until level 69. Keep in mind that you'll only have two glyph slots for each of the three categories available by level 60. These specs can be used for soloing, PvPing or instancing, although they could be tweaked for more focused play, as I deliberately chose survival talents. I encourage you to tinker with these specs if you adopt them while you level, as nothing teaches you what to do faster than seeing it all in action. For more information on how, exactly, to put theory into practice, see how to level in Cataclysm.
Some personal advice
I said before that you should know how you intend to level, but don't forget that Dual-Talent Specialization is available at level 30 and is a very affordable 10 gold. A lot of newer players don't take advantage of this resource, but for really understanding your class and experiencing more of the game, it's invaluable. It can be used to have a DPS spec and a tanking spec, two different tanking specs or DPS specs, a PvE and a PvP spec. On one of my alts, I used it for two arms specs with a few talent points organized differently. For a leveling character, it can be very useful if you don't want to level as protection, to keep your backup spec prot so that if you want to get some faster instances or run some WSG, you can switch over.
It's my opinion that protection is the best leveling spec right now, with arms as second. Fury doesn't gain either of its signature passives (Titan's Grip, Single-Minded Fury) until level 69, although you can still play like an SMF warrior as you go. I mention this purely for people looking for what is likely the fastest and easiest way to level 60.
At the center of the fury of battle stand the warriors: protection, arms and fury. Check out more strategies and tips especially for warriors, including Cataclysm 101 for DPS warriors, a guide to new reputation gear for warriors, and a look back at six years of warrior trends.