Since no Protection Paladin is unhittable yet, Mastery is still king. You won't see a shift in this priority much until you become unhittable. Mastery will continue to be your highest priority stat until you reach the unhittable threshold and additional block is wasted. Beyond the unhittable mark your priorities will shift very heavily towards Dodge and Parry in regards to gear and reforging while only maintaining enough Mastery to remain unhittable. Your gemming priorities would also shift after the unhittable threshold, most likely heavily favoring effective health (Stamina).
Heroic modes break all rules regarding priorities when preparing for extremes. Effective health becomes more important because you have to be able to survive larger hits. In the same regard, healers healing heroics should be able to heal more.
If you are just starting the transition into heroics, don't go overboard immediately. Keep your standard priorities and adjust them as needed, don't go and regem everything for Stamina and think you're ready for heroics. Test the waters a bit and adjust as needed.
"In anything, if you want to go from just a beginner to a pro, you need a montage." /w TankSpot WTB Montage for Raiders.