tl;dr version: Lots of stuff about regaining honor and keeping oaths.
The first quest, fitting, it called Paladin's Pledge and the next one Honor Lost. The final quest is called Keeping the Oath. These set the general themes for the quest line.
The first quest opens (and later quests often repeat this as a component) with a trial of sorts. Before Jenlyns, the captain, can teach you, you must proceed to a location, attract certain monsters, and defeat them in battle.
However, Jenlyns talks of how the people used to look up to paladins. Well regarded, valor, honor, etc... in the style of the knights of old in our own world, or at least an idealized version of them. But during the quest, you're approached by a "free paladin" (Solkzagyl)--upon returning to Jenlyns, he reveals that Solkzagyl was the captain before Jenlyns and is a traitor that stole Oathkeeper, an iconic weapon of the elite Sultanasworn and so losing it was a big blow to their reputation.
Of note is that Jenlyns calls him an oathbreaker, among other such terms.
Over the next few quests, Jenlyns is teaching you/waiting for you to get stronger and prepare to eventually win Oathkeeper back, capture the traitor... and so begin the road of restoring the Paladins' honor.
In time, Jenlyns claims to have discovered a link between Solkzagyl and the Monetarists. He sets up a meet so you can face him, but at the parley Jenlyns actually turns on you and accuses you of being in league with the Monetarists and Solkzagyl.
He is only deterred when one of Jenlyns' own tries to kill him, but to be saved at the last moment by none other than Solkzagyl. Jenlyn does collapse, however, and Solkzagyl takes him back to Ul'Dah.
By and by, Jenlyns realizes you're one of the good guys after all and starts planning to get back at the Monetarists who he realizes were playing him. There's a battle to this effect, said to be a blow against the Monetarists but the end is not conclusive. You're given the last of your AF, and off you go to defend the people of Eorzea.