Download the Dungeon Journal addon - this will make collecting all of the dungeon quests MUCH easier.
There is a bit of flexibility in what level you do things, but I like questing straight to 16 and then starting dungeons so I can run a bunch of different ones in a row. After the update, you now get at level 10, so you can do huge threat in dungeons right away.
For each level range mentioned, I'm mainly focusing on dungeon suggestions, since that's probably what you're most interested in as a tank player. But you always have the option to just quest or grind mobs and skip some dungeons or do them at different levels than I list here. There's no set in stone way you have to level; I'm simply giving suggestions.
Level 1-13: Tirisfal Glades
Just basic questing with a 2 hander. You can leave Tirisfal earlier if you want but doing all of the quests will take you to 13.
Level 13-16: Silverpine Forest or The Barrens
If you go about halfway into 16 now, you'll be level 20 after running Ragefire Chasm and Ruins of Lordaeron, so you can just go right into Wailing Caverns with 
Consecration. Keep questing with a 2 hander but hold onto a 1 hander and shield in case you need it for dungeons. When you go to Undercity, make sure to pickup The Power to Destroy, so you'll already have it when you're ready to run RFC. If you go to Barrens, prioritize finishing the quest chain that starts with The Forgotten Pools (technically there's a breadcrumb quest before this but it isn't needed), as this will unlock the main Wailing Caverns quest for later.
Level 16-18 Ragefire Chasm
At this point, I like to run all of the dungeons. Download the Dungeon Journal addon to easily see all of the quests for each dungeon and where to get them. In Forever, the vast majority of dungeon exp comes from the quests due to dungeon quest exp buffs and dungeon mob exp nerfs, so you really want to make sure you have every quest for a dungeon before you run it.
Level 18-20 Ruins of Lordaeron
If you aren't quite 18+ yet, you can quest in Silverpine Forest or The Barrens or grind mobs.
Level 20-22 Wailing Caverns
If you aren't quite 20 yet, just do a few quests to get there so you can have Consecration for Wailing Caverns. The quests around Camp Taurajo in southern Barrens are great for some quick exp. If you didn't already do the The Forgotten Pools quest chain to unlock the Wailing Caverns quest step, you can just do that.
If you want to skip this dungeon, you can quest in Stonetalon Mountains, Thousand Needles, The Barrens, Ashenvale, or Hillsbrad Foothills. Now that you have Consecration, you can efficiently farm anytime you want. Generally you're looking for hyperspawn areas where you can pull 3-4 mobs at once with little downtime between pulls.
Level 22-24 Shadowfang Keep
If you aren't quite 22+ or want to skip this dungeon, you can quest in Southern Barrens, Stonetalon Mountains, Ashenvale, or Hillsbrad Foothills or grind.
Inside SFK, grab the Black Tome next to Arugal at the end of the dungeon. You can use this later to summon an extra boss in the City of Dalaran dungeon.
Level 24-26 Blackfathom Deeps
If you aren't quite 24+ yet or want to skip this dungeon, you can quest in Hillsbrad Foothills, Stonetalon Mountains, Ashenvale, or Thousand Needles or grind.
Level 26-28 Quest/Grind
The next dungeon we'll tackle is the new Excavation Site dungeon, but there's a lot of tank damage in there, so I recommend getting to 28 before doing it.
In this level range, you can grind or quest in Hillsbrad Foothills, Thousand Needles, Stonetalon Mountains, or Ashenvale. Grinding will be very efficient with Consecration and 
Retribution Aura if you can find some uncontested spots to pull 3-4 mobs at a time with little downtime between pulls.
Level 28-30 Excavation Site
If you aren't quite 28 or want to skip this dungeon, you can quest in Hillsbrad Foothills, Thousand Needles, Stonetalon Mountains, or Ashenvale or grind mobs.
The quest from the Titan Relic will send you to a new area in Northern Mulgore. This spot is fanastic for prot pally farming, with tons of hyperspawning mobs that you can easily pull 3-4 of. Do the quests while you're here and stay a bit to grind if it's open to hit 30+.
Level 30-32 Razorfen Kraul
You don't need to be 30 for this, but you probably will be if you made good use of the spider hyperspawn. If you want to skip this dungeon, just keep grinding spiders or quest in Thousand Needles or Hillsbrad Foothills.
Level 32-34 City of Dalaran
You can do this before 32, but you'll probably be 32+ already by this point. If you want to skip this dungeon, you can quest in Shimmering Flats (Thousand Needles), Arathi Highlands, Stranglethorn Vale, or Alterac Mountains (Hillsbrad quests) or grind.
Level 34-36 Gnomeregan
You don't need to be 34 for this, but you probably will be if you've mostly been following this guide. Gnomer does only have one Horde quest, so it isn't the best exp reward for your time. If you want to skip it, just grind or quest in Arathi Highlands, Shimmering Flats (Thousand Needles), Stranglethorn Vale, or Desolace.
Level 36-38 Quest/Grind
Grind or quest in Stranglethorn Vale, Desolace, Arathi Highlands, Riverglades, Swamp of Sorrows, or Badlands.
Level 38-41 Riverglades Questing
You can also do SM o
Level 40-42 Razorfen Downs / Drowned City
If you aren't quite 40+ or want to skip this dungeon, you can grind or quest in Stranglethorn Vale, Riverglades, Swamp of Sorrows, Badlands, Feralas, or Tanaris.
At level 40, we'll pick up Dual Spec and create a 2nd spec that is full 
Protection. If you have any mana issues, swap to 
Seal of Wisdom. Swap to your 
Pursuit of Justice spec anytime you're traveling.
Level 42-43 Krol'dok
If you aren't quite 42+ or want to skip this dungeon, you can grind or quest in Stranglethorn Vale, Riverglades, Swamp of Sorrows, Badlands, Feralas, or Tanaris.
Level 43-47 Zul'Farrak and Uldaman
If you aren't quite 43+, you can grind or quest in Feralas, Tanaris, Stranglethorn Vale, Riverglades, Swamp of Sorrows, or Badlands.
Level 47-49 Maraudon
If you aren't quite 47+ or want to skip this dungeon, you can grind or quest in Feralas, Tanaris, Searing Gorge, Azshara, or Felwood.
Level 49-51 Alcaz Prison
If you aren't quite 49+ or want to skip this dungeon, you can grind or quest in Hinterlands, Searing Gorge, Azshara, Felwood, Feralas, or Tanaris.
Level 51-53 Sunken Temple
If you aren't quite 51+ or want to skip this dungeon, you can quest in Hinterlands, Felwood, Un'goro Crater, or Azshara.
Level 53-55 Grind/Quest
If you still have Un'goro Crater questing left, that's the best thing to do at this point You can also knockout the Western Plaguelands quests and possibly grind at the farms if they're open.
Level 55-57 Blackrock Depths
At this point, it's best to just start farming endgame gear and not worry about any open world questing or grinding anymore. BRD has tons of quests, early endgame gear, and potential Pre-BIS. If you can't find a group for whatever reason, you can quest in Hyjal, Eastern Plaguelands, Western Plaguelands, Winterspring, or Silithus
Level 57-60 Blackmaw Hold
You can also do Hyjal questing in this range.
Level 58-60 Shaper's Terrace, Stratholme, Scholomance, Blackrock Spire, Dire Maul
These are the endgame dungeons that will drop your Pre-BIS gear, so it's good to get started on the grind while you're still leveling.
Paladin
Protection
Paladin is a spell-based melee 
Tank specialisation that brings tons of utility and excels at mitigating high volume, low damage hits due to block. 
Judgement and 
Holy Strike are used for single target threat, 
Holy Shield gives a combination of threat and reduced damage, and 
Seal of Fury amplifies your auto attack to do more damage and take less damage.
Blessing of Freedom or 
Cleanse.
