What type of deck are you running? Mages (and Priests) have an insane amount of innate board control due to their spells. Fireblast, Fireball, Arcane Missiles, Frost Bolt, Cone of Cold, Polymorph, Pyroblast, the list goes on and on. These spells range from one to eight mana, which means they have an answer to everything at all stages of a game if played correctly.
You can't play a trading game against Mages; they were made for it. Which is why slower decks have such a hard time. As soon as you put something down, they'll remove or neutralize it over and over again until you drop your guard. It's what they do and it's what makes their Hero Ability so strong. A good way to beat Mages is to pressure them early and hard, don't give them any breathing room to obtain board control as they please.
As a Warrior, you have two viable options. First, you can make an Enrage/Charge deck. These hit hard and they hit fast, which is exactly what you want against a Mage. Unfortunately these types of decks rely a bit too much on the synergy of your cards. You need to have the perfect cards in your hand and play them at the correct time to pull off successful combos. To do this on a consistent basis, you need to have good drawing power and card advantage, something Warriors currently lack. Well not lack, more like unreliable. There are many factors that go into an Enrage/Charge deck and I found that luck is one of the more prominent ones. Fun, but not really my cup of tea when playing Ranked.
The second, and more reliable, alternative is to build a deck around weapons. Weapons are arguably the most cost efficient abilities in the game (don't be afraid of losing health!). Like I mentioned earlier, it's extremely difficult to trade blows on a consistent basis against Mages and come out on top. However, weapons give Warriors the ability to do just that! You have the choice to keep attacking their minions or take a swing at it and go in for the kill if you feel the time is right.
By relying on weapons instead of minions, you can effectively trade blows and destroy their minions while not having to worry about getting destroyed/negated every turn, which leaves room for your other minions to stay on the board and attack. It's your own version of board control. Having fewer and less strong minions on the board may also make their spells cost-inefficient. Sometimes they'll waste their AOE and high damage spells against you because they need to do something in order to stop the onslaught and keep the pressure off.
Spells cost a lot of mana. Mages try to gain board control early on by negating any and all monsters you put down and try to maintain that grip throughout the match. Fireblast let them do just that. Fortunately if they spend their limited resource and effectively fail in doing so early on, they'll put themselves very far behind. Weapons let you trade blow for blow against their monsters, which means they'll waste turns and mana casting Fireblasts other damage spells which may not even slow you down (you're effectively a 2-10 attack / 30 health + armor monster stomping around the playground!).
There's many variations of Weapon decks. I've found weapons coupled with some drawing power and minions with charge to be quite effective. You're not invincible and you won't beat everybody but these types of decks effectively gives you the opportunity to trade blows against any other, which is really all you can ask for. I consistently beat any and all type of decks in 3-Star Masters (even Murlocs! *shudder*).