The base attributes of each race are standard and increase at predictable rates with leveling. Obtaining equipment with bonuses to the various attributes is essential to the paladin's development. A table showing the leveling progression is available at Base Stats Table. Choosing the best attribute bonuses is a challenging and ongoing process.
Strength
Strength affects the base damage a paladin can do with melee attacks and affects the amount of damage that can be blocked with a shield. The natural leveling of a paladin enhances strength faster than agility, intelligence, or spirit. Equipment that adds to strength will increase the damage done with each attack slightly. Depending on your play style and paladin build you may want to buff this modestly.
Agility
Agility affects the melee chance to hit with a weapon and increases the critical hit chance. Agility increases slowly for the paladin and for certain builds increasing agility is very effective. Retribution tree paladins with the vengeance skill can boost their damage significantly with extra agility.
Stamina
Stamina adds to the characters hit points (or health). Stamina is the other attribute that increases rapidly as the paladin levels. Being able to absorb more damage is always a good thing for a paladin. Functioning as a primary tank or off-tank always benefits from extra stamina.
Intelligence
Intelligence adds to the characters available mana pool. Intelligence builds slowly as a paladin levels. Paladins are a hybrid class of melee and caster. The caster part of the paladin needs more mana. For support healer or primary healer extra mana is a necessity.
Spirit
Spirit increases the regeneration rate of health and mana when not in combat. Spirit helps shorten downtime between fights. Paladins rarely have much downtime between fights due to self healing and Blessing of Wisdom that can accelerate mana regeneration.
Discussion
There are three talent trees for paladins Retribution, Protection, and Holy. Paladins that primarily focus on the Retribution skills will benefit from Agility, Intelligence, Stamina, and Strength to help boost their critical strike chance and mana pool. Protection tree will benefit from stamina and strength. Allowing them to absorb more damage and block more damage with shield. ( testing to determine the amount of affect on shield is needed ). Paladins focusing on the holy tree will benefit from intelligence, stamina, and strength. Intelligence to help boost their available mana to make them more effective casters. Most paladins will have high stamina and strength values, a holy paladin should put higher focus on intelligence than strength due to the fact that it will increase spell damage and healing. A holy paladin will not primarily deal physical damage and is thus not so dependant on strength.