The quality of your equipment will determine how effective you are as a paladin. Since we are a hybrid class that doesn’t specialize in one area, we need to rely on our gear to shift us in one direction or another. If you want to be a great healer your gear will need to primarily have intelligence and + healing. If you want to engage in melee you will need to get strength and crit gear. It would be nice if you could have gear that covers all of your stats, but then it would become overpowered so you will usually find gear that only has two or three stats at best. Some people try to split their gear between play styles by having half go to healing and the other half go to fighting. This is generally a bad idea because the game is designed to force you to have your gear go down a particular path. When you fight, your enemy will have more strength then you and beat you down faster then you beat him down, and the benefits to your healing or spell damage will be to low to save you. To solve this most players keep different sets of gear with them that they can switch out for different situations. If you need a tank you pull out the plate and stamina gear. But if you need to heal you pull out your Int and healing gear. This is certainly not restricted to paladins alone. Nearly every class has to go through this but after warriors paladins are probably the second most gear dependant class in the game.
If you want to be a melee damage dealer then your three most important stats are strength, stamina and melee critical strikes. You will also want to put in a few pieces of intelligence gear for extra mana but try to avoid magic damage since you won't benefit from it very much. If you are going for a holy warrior build that deals damage through seals and abilities then you will want some spell damage. You will also want to load up on intelligence for a bigger mana pool and stamina for survivability. This is especially useful for protection AE grinding.
If you are a pure healing character your priority stats are +healing, intelligence and mana regeneration. You can regen mana in two ways, either through spirit or through gear that gives mana every five seconds. Usually the man/5 seconds is better because spirit is a really weak stat and requires you to not be casting for it to work.

Plate, Mail, Leather Or Cloth?
In the game there is a hierarchy for armor. Cloth is the lowest and weakest, then leather, then mail and then plate. Generally you will want to wear the highest armor you can as a paladins because of the increase to your armor rating. Until level forty the highest armor a paladins can wear is mail, at which point they can learn to wear plate from a class trainer. Once problem is that except for class sets and a few special pieces, plate is usually only geared for melee warriors with stats like Strength, stamina and melee modifiers. If you want to be fully armed but still be a good healer or support character you are going to have to do a lot of searching and running through dungeons to get pieces that benefit things besides melee. This has led some paladins to exchange a few of their pieces for other armor types instead of plate.
Mail is just below plate and is the easiest to switch out. Since shamans are reliant on mail this is where you will get most of your spell damage modifiers like spell crit and healing. The more of a support character you are, the more pieces of mail you can get away with. As you level closer to sixty though the difference between the two becomes greater and you will be making a bigger sacrifice.
Leather will rarely have any stats that you will want that you couldn’t get on plate. The only exception would be + Healing, but druids will need that more then you. The only time you should be wearing leather is in your first ten levels when mail is harder to come by.
Cloth is a really difficult choice. On one hand it offers you virtually no armor protection. But on the other it makes up for that with huge boosts to caster stats. The only time it is ever good to wear cloth is when you are primarily a healing based paladin in raids. In these situations armor is not worth very much but casting stats are, and since cloth has more opportunities for +healing then any other armor type it is actually a good idea to have some of these. But, you should still try to limit how many of these you wear at a time and make up for them by wearing more plate.