Current observations:
Our specials are based on a 2 roll system, our normal (autoswings) are a one roll system. This simply means that hit and expertise are even more important to us than before.
You need 8%, not the BC 9%, to be 2H melee hitcapped vs skull level mobs (bosses).
You (still) need 26 expertise (6.50%) to be expertise capped, not the 6.25% reported lately.
All melee classes seem to suffer a 4.8% crit suppression vs skull mobs; this means that your melee critrate will be on average 1.8% lower than your character sheet implies (HotC covers 3% of this, procs from librams and such not accounted for).
All spell attacks have a 3% crit suppression vs bosses. Because of HotC, we do not notice this at all; also only exorcism and holy wrath are affected by this.
The spell hit cap is still 17% - the only skills we have that are affected by this are exorcism, holy wrath, and consecrate ticks - so this is of little importance to us.

(In order of importance!)

If you are looking for stat weightings I suggest you use one of the spreadsheets at the top, as they vary greatly depending on your current gear.

Hit See Observations
32.8 rating gives you 1% hit. At level 80, we require 263 hit rating, or 8%, to be hit capped on white swings, specials, and judgements. Note that Exorcism and Consecration are considered spells and use the spell hit table, thus we can still miss with these abilities. As of 3.1 hit cap is very important, and quite a bit easier to attain - you need to be hitcapped in order to maximize your dps, so gemming for it isn't a bad idea. Hit is as good or better than STR until you are hitcapped, and then becomes worthless after the cap, so gear appropriately. If you always raid with a draenei, you have the option of gearing for 7% hit due to their racial.

Strength
Our DPS stat to stack after the hitcap, as we have various talents that multiply it's effect. 1 STR gives you 2 AP baseline, multiplied by 1.15 from Divine Strength (Tier 1 Prot) giving us 2.3 AP per STR when specced. This number is further affected by buffs such as BoK. STR also increases the strength of our utility spells such as JoL/SS/AoW via talents. It is recommended that you gem STR after you are hitcapped.

Expertise
Introduced in late BC, this stat allows us to remove dodges from the attack table - you cannot remove parries from the table, but you only get parried from the front, so don't attack bosses from the front! 8.2 rating gives 1 expertise; you need 214 expertise rating (26 expertise, 6.5%) to reach the cap. If you are a human using a sword/mace you need 23 expertise (189 rating), and if you are a dwarf using a mace you need 21 expertise (173 rating) to reach the cap due to racials. Capping this stat is a significant dps increase vs uncapped (or none at all) as it affects our whites, strikes, and SoB. You ideally want to cap this stat alongside hit in order to maximize your dps and this is possible in 3.1 with the amount of expertise on gear. You have the option of gemming for expertise to get caught up/close to the cap, but there should be enough on BiS gear naturally that this isn't necessary.

Crit See Observations
We are quite reliant on critical strikes to do damage. You can never really have too much crit, but it is not worth gemming for it, gem for STR instead. You need 45.9 crit rating to gain 1% crit at 80. This stat gains no benefits from raid buffs, but you get more per itemization point from crit than you do AGI. This stat also increases your spell crit rating, making it flat out superior to AGI.

Agility
We need 52.08 agility to gain 1% melee crit. Like stated before, crit is flat out better, however AGI does scale with raid buffs such as BoK where crit does not. Often found on leather, mail, or sometimes weapons, but not on plate.

Haste
Haste received some buffs in 3.1; namely for paladins we get 30% more haste from each rating point. Haste increases white damage and SoB/SoM damage by giving you a few more attacks against a boss; haste does NOT decrease the GCD on our instant strikes or instant spells. You will find plenty of it on our sets and pieces, don't enchant or gem for it. You need 32.7 baseline haste rating to gain 1% haste at 80, but adjusted with the 3.1 changes paladins require 25.2 haste rating for 1% haste.

Armor Penetration
ArP was buffed in 3.1 by 25% - but it still only affects 40% of our damage, meaning we received about a 10% increased benefit from this stat (as opposed to warriors who received a 25% increase). 12.3 rating now gives you 1% armor piercing; unlike BC, you can no longer fully ignore boss or player armor via this stat. ArPen does NOT increase damage done by seals, just white damage, CS and DS.

Attack Power
Most of our skills scale off AP, but this stat is now bottom of the melee barrel - STR is just so much better. AP isn't really seen on plate (so you often don't have to worry about this) but you will run into it if you dip into leather and mail. Note that despite AP having a 2:1 item stat budget, it is still far weaker than STR as we have no talents that boost it's effect. When comparing or considering pieces with AP vs plate, you need to look at the item stats/level as a whole.

Spellpower
Bad item stat for us. Spellpower increases some of our skills' coefficients, but at a rate much slower than STR/AP, and does nothing for our white damage and instant melee strikes - CS and DS gain nothing from spellpower. Avoid this stat (easy to do, since none of our ret gear has spellpower).

Intellect
As of 3.1, INT sucks due to JotW/SA changes. 1 INT gives you 15 mana and a negligible amount of spell crit; you need 166 INT to gain 1% spellcrit. INT will increase the mana you get from DP, and your total mana pool, nothing else. You will only find int on hunter/enh shaman gear and it is rare to find a piece of mail better than plate/leather.

Stamina, Armor
Ultimately, stam does nothing more than keep you alive in situations where there is raid damage, and in wrath there is a lot of raid damage. Most of the damage is magic (not mitigated by armor) therefor armor class does not matter to us, as we have no Armored to the Teeth talents like warriors or deathknights. You'll find all the stam you need and much much more on all wrath gear.