This is a quick summary to get you up to speed with some of the more major changes. The level at which almost all abilities can be obtained have changed, but the talent trees themselves are pretty much in the same shape, but with talents tweaked in a lot of cases.
Changes to existing abilities
Divine Intervention Gone! That's right, when you and some random DPS are the only two left and Ardent Defender has already gone off, that last chance to save yourself repair costs is gone. No news yet as to the exact reason, but we no longer have the wipe prevention (after all, that random DPS might be a druid, priest, shaman, paladin or engineer). We also don't know if we're going to receive something in return at the moment or not.
Blessing of Wisdom Gone! This has been rolled into Blessing of Might. However, there is still a talent for Improved Blessing of Wisdom in the holy tree right now, but that could be on the list of things to disappear.
All Greater Blessings Gone! All blessings now work as both a singular and greater blessing, and instead of casting them class by class, they're now raid-wide. Oh, and they also last a full hour like all of the other raid buffs.
Blessing of Might Adds 10% attack power and a small amount of MP5 when you get it, but likely scales with level. It has also been shifted all the way up to level 56 instead of level 4. Improved Blessing of Might still exists in the retribution tree, which isn't in sync with Blizzard's claim to be removing talents that buff buffs, but we're seeing a lot of that in talents.
Blessing of Kings Now the same as the revamp of Mark of the Wild, which are both obtained at level 30.
Blessing of Sanctuary Gone! Well, kinda. Blessing of Sanctuary is now just a passive talent instead of an ability. It still reduces damage by 3% and gives mana return on dodges, parries and blocks. The upside is that you can use the revised Blessing of Kings just like everyone else instead of needing to do Sanctuary separately.
Resistance Aura All of the resistance auras have been rolled into a single one to cover everything. This will knock two buttons off of our aura bar and make it easier to just assign someone to cover 'resistances' for the raid.
Holy Shield This is a very poorly worded talent. It decreases the critical strike chance of incoming melee hits by 6% passively at all times if you have this talent, thus getting rid of the need for defense rating. Completely separate from that, it's a talented ability that does all of the things that it always did. One note is that during the class previews, we were told that the charges on the ability were going to disappear, but that doesn't seem to be the case at the moment. This could possibly be one of those things they haven't gotten around to tweaking yet, but we've yet to see.
Crusader Strike We finally have another baseline, early-on melee attack ability! This is something we've been sort of lacking on as a melee class in general. Against solo targets, this will probably replace Hammer of the Righteous as protection and will help the overall boredom of leveling a young paladin in general. Taking its place in the retribution tree is Improved Crusader Strike, giving ret a damage boost on the skill.
New Mounts There are new paladin mounts for draenei and tauren. Since they're both larger races and sort of look silly riding horses, they're getting paladin themed versions of their racial mounts. Everyone else gets to keep the existing pally ponies.
Divine Light This is going to be a new healing spell for paladins. First off, it appears unfinished and other than the obscenely high mana cost, it just duplicates Holy Light currently. This is likely something that we'll never use while tanking, but it could be helpful between things while soloing at lower levels. Still no real details on what the level we'll get it at, as we can presume that it's just filler right now.
Healing Hands Imagine something like Wild Growth but always centered on you. This is going to be an instant-cast, but according to current numbers, it will have a very high casting cost. But, if you're able to keep as unlimited mana during intense fights as you can on live realms, this would be a great way to help out yourself and your healers.
Missing in action
Guardian of the Ancient Kings This was a new skill mentioned in the class previews a while back. Currently, the level cap on the beta realms is 82, which means that this level 85 ability wouldn't even be available for testing were it in. As something that would require its own new art for a guardian creature to help the paladin, this will probably take some time. There is also the logic to do different things depending on the spec of the paladin that summons it. Overall, we'll likely not see this for a month or two if we're lucky.
Blinding Shield The spell appears to be in game but not attached to the paladin class yet. Also, this ability has a short cast time, which was supposed to have talents in the protection tree to reduce it down to an instant-cast, but those features also don't appear to be in yet. Essentially, not yet implemented (NYI).
Baseline Holy Shock This idea might have just been scrapped. Holy Shock, a 31-point talent in the holy tree was supposed to follow suit with Crusader Strike and make itself available to all paladins. However, as it stands, it is still sitting square in the middle of the holy tree. This was supposed to offer an instant healing ability for retribution and protection to make use of while leveling, as well as taking full advantage of its offensive capabilities.
The Light and How to Swing It tries to help paladins cope with the dark times coming in Cataclysm. See the upcoming paladin changes the expansion will bring.
Wrath is coming to a close and the final showdown with the Lich King is here. With
Cataclysm soon heating things up, will you be ready?