To compliment the warrior - you need a healing class. To maximise its usefulness you want it to dps as well.

For leveling/grinding go shadow priest - VE and mindflay it will heal and high dps at the same time.

A shammy also rocks - My 70 warrior (MS) has just started dragging my 60 shammy through outlands, windfurry is awesome. Casting dps is great as well.

Pallys and druids are (basically) good for healing only - the bulk of their dps come from melee or close range spells. Boxing with a melee clases in support is hard.

Pally would probably be the choice if you want to pvp. People don't behave like npc's.