Chromaggus is the last boss standing between you and Nefarian. They adapted his 'curse' mechanic for the game by having him put various 1 mana cards in your hand that either do damage to you or buff Chromaggus in some way like heal him, or make his minion or spells cost less as long as you hold them in your hand. You have to "play" them which burns your own mana. His deck consists of many Druid cards like Swipe, and Claw. One particularly troublesome minion he has is the Chromatic Dragonkin. This minon gets +2/+2 every time you cast a spell and those nasty debuff cards Chromaggus gives you count as spells. You need to take the Chromatic Dragonkin out with minions which means a board presence is key before you start playing any spells. Your other best option would be something like Frostbolt.
I went with a Mage deck. You get a Flamewaker for defeating Vaelestraz. I tried to make the fact that the debuff cards counted as spells work for me by making a deck with Mana Wyrms and Flamewakers. Sorcerer's apprentice makes the debuff cards cost 0 mana so you can get rid of them, activate your Flamewakers and buff your Mana Wryms. You can try to protect your minions from Swipe and his other spells with cards like Counterspell or Spellbender.
Chromaggus has two Faire dragons in his deck which he tries to play as soon as he draws them. Sometimes you have to sacrifice a Sorcerer to kill them but a Snowchugger would be a better option.
Here's the deck I used:
Mana Wyrm x2
Sorcerer's Apprentice x2
Arcane Intellect x2
Mirror Entity x2
Spellbender (or another Counterspell)
Flamewaker x2 (should have gotten from Vael)
Water Elemental x2
Pyroblast (any large minion would do as well - Boulderfist Ogre, Giant, etc)
If I hadn't killed him that turn, I would have pinged one of the Chromatics with Fireblast and killed him with Blizzard.