"Don't deny your rowdy nature, paladin. And don't take advice from old people."
from season 1 episode 25, "His Hero."
Pendleton Ward had included plenty of hints in previous episodes of Adventure Time. Finn had previously referred to his alignment and his inability to act against it. In episode 23, he refuses to kill a Neutral creature, as he will only kill evil ones. In episode 24, he tells Bubblegum he can't beat up the Ice King for no reason. "It's against my alignment!" The kind of character that worries this much about not transgressing against his alignment is, of course, a paladin, so RP gamers watching had known that Finn was a paladin before the old lady calls him one in episode 25, and before Ward explicitly acknowledged the fact in an interview on Wizards' Dungeons and Dragons website.
The name derives from a Roman term for a palace official, and thence came to be applied to Charlemagne's Twelve Peers, and later to all chivalrous heroes. Gary Gygax (Supplement I: Greyhawk 1976 -- spelled out further two years later in the PHB) took the term for such a paragon of knighthood and added to it the sanctity of the ideal crusader -- a crucial development that goes beyond even the importance of the Christian identity of the Twelve Peers contrasted against the background of their Saracean foes. This development gave games from D&D and its descendents, including WoW, the name for their holy warrior classes, when the obvious term in the West would have most likely been crusader. Perhaps the denigration of that name mitigated against its effectiveness as a choice. It is interesting that the original uses of the name would have better suited it as the name of a member of a royal order of knights bound to a king -- such as Finn and Jake play in season 2, episode 3, "Loyalty to the King" of Arthur's Knights of the Round Table. But perhaps the later, especially those devoted to the Quest of the Holy Grail, will help us to bind the two concepts together, with paladins being Lawful in so far as they are bound to a king or other divinely ordained ruler of law and Good in so far at they are devoted to their deity.* This could provide a fun source of tension as well for the character, when there is the potential for loyalty and holiness to come into conflict.
As Adventure Time so bluntly points out, the paladin uses violence for ends that are both lawful and good: in particular, the protection of the weak. For more on the chivalric code, see here and here. Crafting a bipartite code for a paladin that spells out in one part his duties to his leige lord (or lady) and in another, his duties to his heavenly Lord (or Lady), would go a long way towards world and character building, whether for fiction or gaming.
In addition to Mallory's Morte d' Arthur, I'd rewatch Ridley Scott's Kingdom of Heaven, although I did not like the director's cut which seemed to step away from the fine line of showing the good and bad on both sides and towards being obviously anti-Christian. Therein are examples of the holy warrior struggling to be bound to both God on one hand and to his King and kingdom on the other.
* Let's not pass up the opportunity to link this Lawful Good entry.