Any healer class will work, every one has it's pros and cons. I think a good wiki writeup would be easier so I can reference this in the future
It really comes down to player skill of the healer and your playstyle.

So #1 - Skill of healer involved:
It's easy to see the difference between a good and bad healer, for Arenas though there is a tier above that - your healer needs experience, although if your just starting out yourself you can let this one slide as your both on a learning curve. Now what do I mean by experience? Hopefully they have reached 1850+ rating.. 2k+ preferred previously at one point. Their gear also needs to be of high quality or at least comparable to yours.
How do I gauge a good healer from an amazing healer? Try them out, start a team fresh and play 20 games, possibly more. At the 1500 rating you will play easy teams and as you move up the bracket they already have a feel for your playstyle and adapt to it. The #1 indicator I use to identify an amazing healer is when I no longer need to look at my health bars and can focus on offensive. If your able to do this then it is a keeper, no matter the healing class.
#2 Your playstyle:
Are you offensive or defensive?
Priest/Druid are more offensive type healers while Paladin/Shaman are defensive type.
Offensive Healers-
Priests:
Pro's- to this is that they can assist you in ensuring easy Line of Sight kills. The priest - ability to AoE fear, disrupting their offensive and pulling opponents away from LoS objects, pending if your alliance side can root/stun for 2 seconds with their racial. Pain Suppression is also a Boon to avoid being insta-gibbed on your characters, but if you do not drop targets quickly it is only going to be an uphill battle.
-Has powerful AoE Heals
-Very good HoT's and ability to heal while mobile
Cons -do not have the mana efficiency to outlasts opponents
-Very Squishy


Druids:
Pro's- able to avoid damage by running away effectively, or shift into Bear form to sustain damage while you assist.
-The greatest strength of a druid is the ability to lock down a target in place long enough for you to take care of. The element of surprise using Pounce while they are in stealth cat form, Roots, Feral Charge, Cyclone, Bash, or a combination of any provides you ample amount of time to lock down a target and blow it up.
-Able to heal burst damage better than anyone.
-Has 1 AoE heal
-Able to heal while mobile
Cons- Also do no have the mana efficiency to outlast opponents, they are only able to last via running away and drinking which is usually not an option with this setup until later stages.
-Once burst heal is used - healing effectiveness goes way down

Defensive Healers-
Shamans:
Pro's- Resto Shaman have very potent Chain heals which are able to heal the main and top off an AoE you may have taken. Nice burst heal via NS, and lesser healing waves for quick heals in a punch.
-Adding an extra grounding totem is huge, you'd think 4 is enough but having 5 is insane!
-A Tremor Totem they can drop if you run out of range from your own. (this saves many lives)
-Mana Tide for long lasting fights
-Earthshield to be placed on your main or on the healer, extra survivability
-not squishy
Con's- Shamans may have a lot of pro's but they have no instant cast heals, and are not mobile at all.
-No abilities to assist in locking down targets, so it is completely up to you to find kills.
-1 Rogue can dominate a Shaman healer as well.

Paladins:
Pro's - Very large consistant Heals.
-Blessing of Protection making melee heavy teams cake.
-Bubble providing 12~ seconds of non stop Heals without worry.
-Wears plate.
-Very mana efficient

Con's - 0 instant cast burst heals (Holy shock buff may be changing this soon)
-Paladin stun has a huge resist rate on it, I'd say 50%, so locking down targets is not plausible. Your on your own.
-non mobile, meaning easy lockdown.

There is my assessment of what you can choose from. Besides the points I make, it really comes down to how well you work with your teammate, your communication, and if it's your style.