With almost every patch, leveling a Warrior has become more ensily accomplished, which lead to the current status of the Warrior leveling nigh matching that of all other quickly leveling classes, mostlyu due to the increased emphasis on questing as opposed to long-term grinding.
As far as speed and style, this largely depends on which talent tree you can choose to emphasize, Fury being first amongst leveling speeds, arms second, and protection a very distant third. However, all things considered, each suits a differing player and variety of fun.
In part Fury leveling is focused on killing fast and effectively through extremely fast attack speeds combined with a high critical and hit rate if possible. These stats combine to generate a blender-speed whirlwind of (insert two weapons of choice) when mowing down mobs.
Probably downtime is least with this build as well, lending itself to taking down opposition with minimal time spent and thus lessening the time the enemy spends beating on you, always helpful. When combined with bandaging, this reduces downtime to almost nil.
In spite of the traditional build of fury is indeed dual-wield, there is also the variant of two-handed fury that boasts a leveling speed somewhere between that of dual-wield and an arms build, yet for many this difference in play style is more interesting/more fun for leveling regardless.
Through the experience two-handed-fury builds are a good change of pace from the usual fury grind and mix the blinding speed of dual-wield with the big hits of an Arms build, the result is pleasing and a undeniably viable choice for all looking for something a bit more unique.
As the second fastest leveling style, however, arms build presents itself as the greatest PvP build for both leveling and post 70 battlegrounds/arena's, making it one os the more viable choices for those playing on PvP servers.
To some extent Mortal Strike is where this build really picks up as prior to gaining an instant attack arms DPS is sorely lacking as well as being exceedingly dull for the most part, a big turn off for most players is hitting 1 or 2 buttons from 1-40.
Fortunately, post 40 a mortal strike build picks up significantly, finally starting to catch up to the otherwise blinding speed of fury from 20-40 and becoming a great equalizer in any PvP battles you encounter while running about questing zones.
In a word this's a good change of style/pace for those tired of dual-wield or being slaughtered by other players frequently, but for those seeking to maximize leveling speeds.
By far Protection is the slowest solo-leveling specialization for any warrior, no matter the gear nor personal playing ability, protection is simply too low on the damage output and downtime management to be a viable solo-alternative to either fury or arms.
However, when teaming frequently this becomes an entirely different matter, any warrior with some good friends seeking to spend more time in instances than outside grinding will find protection suddenly that much more viable.
It's not necessary that instance farming is the fastest way to level, but it can be more fun for many players, additionally when questing a tank can always come in handy for tougher/elite group quests, making protection ideal for someone with at least one or two buddies at all times.