I have been out of wow for a long time. I have recently begun to play an arms warrior with 4 friends (mostly dungeons and some pvp). What are the best add-on's to help level a warrior?
Over the years Blizzard has been steadily taking the best ideas from the UI customization community and integrating them into the base UI. For example, the game now has a built-in version of QuestHelper which shows (on your map) where to go to kill monsters for quests and turn them in afterward. Frankly, there are no "vital" leveling addons anymore.
Some addons can be useful, of course, but it depends more on your own play style rather than "here's a list of what you need to play the game".
My advice is to just start playing with no UI addons, and wait until you find an itch that needs scratching before you bother installing any.
I definitely agree that there are no required "leveling" addons, unless you're talking about leveling professions, in which case addons like Gatherer, and Fishing Buddy and similar are useful.
The only addons I ever bother to install are all instance based. Omen, Healbot, DeadlyBossMods, etc.