From WoWWiki

This article or section is a miscellaneous stub. You can help expand it by editing it. If appropriate, you might want to import some information from a database site - see Fansites for listings. Pages linking here may have clues as to what the page should contain, or perhaps the discussion page.

Horde Warrior Mail Guide for Leveling

This isn't the end-all, be-all for gear guides for leveling Warriors and Paladins, but I think it will be a handy reference if you are considered your armor might be a bit behind. Note that this guide only goes up to Level 40, since you won't need Mail after that.

Levels 1-12

Whatever you can find at this point that has armor on it is a great start, unless you can find some low level quest rewards, such as Bronze Mail Bracers from Eversong Woods. But if not, have a decent weapon and keep fighting onwards.