As a plate wearing class, you actually wear mail at lower levels; you are allowed to begin wearing plate at level 40, and won't begin receiving plate quest rewards or dungeon drops until you get into level 40+ content.
From past experience I can say it will probably take you almost until level 50 to upgrade all of your old mail gear to plate from rewards/drops.
As a retribution paladin, you will want plate (mail below level 40) gear which has Strength. You'll occasionally see gear with Dodge or Parry secondary stats; these are designed for Protection paladins (and other tanks), and while you can use them if they're otherwise a significant upgrade from what you have now, they won't benefit you as much as gear with Hit, Expertise or even Haste.
That said, don't worry about the secondary stats too much, at least until you get to level cap. Having a less-than-ideal secondary stat on one or two pieces isn't going to affect your game noticeably, though if you have less than ideal stats on most or all of your gear, you will definitely have difficulty with level-appropriate content.
Finally, check your map and quest log to make sure you're in a level appropriate zone; if the zone's quests are green or gray, it's time to move on (unless you really want to see how the zone's story ends); hit the Warchief's Command Board (Alliance: Hero's Call Board) in any major city to find a new quest zone to go to.