Finally you have control of Cairne. Give him any +strength items you have and anything else you think he might put to good use. Use his stomp ability when he's surrounded by enemies to stun them. For that reason you may consider giving him the big +mana item you have. It's really up to you. The first thing you should do is eliminate a possible nuisance. There are thunder lizards just west of your base. Kill them off. They don't drop anything but you can use the experience. Now keep your forces home a short while to do some defending. Build up your base as usual and get any unit upgrades you like and prepare to do the optional quests:

Optional Quest: Freeing the Wyverns
Southwest around the plateau you start next to is a fountain which has been defiled. You're supposed to get the Glyph of Purification from the local Centaur Khan to purify it. Begin this journey once your base has enough defenders to hold back the humans. Head to the north out of your base and at the first opportunity head west. A cutscene will reveal that the harpies have enslaved the wyverns. Kill off the wyverns and continue to the west. Kill the quillboars and razormanes you encounter (big razormane drops a health stone) and head on to the north where you will encounter another large group of enemies. Kill them off and you'll receive a periaph of vitality (+100 hp when held). Now continue on this path to find many more harpies to kill. At the end you will encounter the Harpy Queen who will drop a pendant of mana. The Wyverns will then be released from captivity and you'll be given command of them and now be capable of training them at your base.

Optional Quest: Purify the Fountain
This is not as hard as the wyvern quest. Gather your forces and head north. Almost directly north of you base you'll find a goblin laboratory being guarded by several centaurs. Kind of lets you know we're headed in the right direction eh? Now head north then east around the mountain to fight the Centaur Khan. He's really tough like they always are so prepare to do some chain lightning and spirit wolf action with Thrall and some major stomping with Cairne. Shouldn't be too hard if that's done. When the Khan dies he'll drop the Glyph. Now return to the fountain and it will be purified, allowing you to heal your units there.

Now to take on the main human base. It's all the way to the north as you should already be able to see. I first destroyed the small light blue base to the west of that though. It's on the ground level so you don't need the zeppelins to get there. Also with that threat eliminated you have a better time focusing your effort on the blue base. When the light blue base is destroyed I recommend you take both heroes, a couple tauren two grunts and the rest be witch doctors and headhunters. I had all my units fully upgraded at this point so it wasn't very hard. The most challenging aspect of this is probably the air units. Thrall can use his chain lightning to damage them pretty well and the witch doctors can use healing wards to fend off some of the damage your units will inevitably take. When the base is finished off you're victorious.