1) Very strong early game aggression, with health-buffing out of Blizzard range, and forcing the Mage to freeze every turn to not die immediately.
2) Charge / weapons, which can't be frozen.
3) Healing. Healing spells by default are twice as mana efficient as damage spells, completely trivializing things like burning with Pyroblast.
First, understand that different Mage decks will generally play in different ways. Some go heavy on board position, some do not. But some common things you'll encounter in many decks are:
1) Pyroblast. The Mage will be able to easily hit you for 11 damage in one turn starting at turn 10, and possibly more if they can Pyro + Frostbolt (though often Frostbolts are used up in early game control). So keep an eye on your health and don't let it dip below these numbers.
2) Ice Block. Most Mages will run at least one Ice Block, though some do not. Have a gameplan for this; proc is the first moment you can, but try to get their health as low as possible for the final blow. That is, if you have multiple minions, make sure you attack in such a way that the Mage is as close to 1 health as possible when you do your final hit. If possible, try to keep a direct damage or charge ability in your hand for the next turn incase they try to freeze you, so that you can deliver the last damage. Remember that the sooner you can proc the first Ice Block, the lower the chance is they'll have drawn their second.
3) Alexstraza. This is probably the thing people have the most trouble playing around. She can be used to either heal the mage up after an Ice Block or to knock your own health to 15 to kill you in a few turns. There's a few counters for this. First, running Big Game Hunter is a good option nowadays as most decks that aren't aggro decks are running something large enough to kill with it (Ragnaros, Giants, etc.).
Beyond that, the key is to realize that the Mage will expend their entire turn dropping Alexstraza and to capitalize on that. If playing with healing cards, do not heal yourself until Alexstraza comes out unless you're in range to be killed by Pyroblast. You want to wait until AFTER the Alexstraza drop to do this; otherwise, your healing will be wasted.
If they use it defensively, a major key to remember is that the Mage cannot freeze, cast Ice Block, or aoe your board on the same turn they drop Alexstraza. So for example, if the Mage has used up both of their Ice Blocks (they usually won't use Alexstraza until they have), if you fill your board super big at this point, you win: If they Alexstraza themself back to 15 health, you do 15 damage to them that turn. If they aoe your board, they're at 1 health and are killed by direct damage.
Class-by-class. You can look up specific decks online, but I'll give a very brief outline on how classes manage Mages for the most part.
1) Warlocks. Go EXTREMELY aggressive. As in, you should have 20 damage or so on the board by turn 5. Blizzard aoe is very expensive with the nerfs, and you have plenty of access to abilities that buff minion health. So swarm the board, and the first turn they don't have a freeze, kill them. They'll be so much on the defensive freezing you that they won't be able to cycle cards to draw into more freezes.
2) Priest. Make use of the hero power to heal yourself. Use big minions and health buffing abilities to safely fill your board without risk of Flamestirke. Don't be afraid to use Holy Nova as a healing ability rather than a dps one if you need a little extra health.
3) Rogue. Be very aggressive, like the Warlock. In general, charge minions are very effective for Rogues, especially if you play Shadowsteps.
4) Druids. Druids have been playing a late-game ramp variant against Mages. I can't elaborate on it too much, but Healing Touch is one of the keys. Ancient of Lore can be used for a little bit of extra healing in a pinch as well. Your hero power is an extremely effective counter to the mage attemping to ping you down, and if you build up some armor (including Bite and/or Claw), it can't be melted by Alexstraza.
5) Shaman. I know there are some anti-mage variants floating around, but I don't really know the details on how they work.
6) Hunters. Heavy traps to slow down the game as well as to MD giants back into the mage, focuses on direct damage from Eaglehorn Longbow and the hunter hero power as well as charge. Shoots for roughly a turn 7 win (the direct damage is pretty dang high). Uses Flare to remove Ice Block.
7) Paladin. Mainly focuses on massive amounts of healing to grind out the Mage's health. Big Game Hunter is basically a must-have to counter the Alexstraza drop since you don't have removal (you'll need BGH against other decks anyway). To put it in context, mages have 38 direct damage, Paladins have 48 total healing (36 if you don't include Holy Light), so they can easily outheal a Mage's damage as long as the Mage doesn't get control of the board.
8) Warrior. Makes use of Armor through the hero power and Shield Block. Alexstraza doesn't eat through armor, meaning if you build some up, they can't knock you down nearly as much. Warriors also inherently tend to have a lot of charge and weapons.