I didn't phrase that right. Let me rephrase: what is a paladin's relation to the church?

They take Oaths, that's pretty formalised, they just express their faith differently. If you want a real life religious teaching on this, 1 Corinthians 12:14-31 is where Paul compares different roles in the church as being different parts of the body. Similar to Clerics and Paladins will be different parts of their god's religion.

Alternatively, you could see a Paladin as a unique multiclass of Fighter and Cleric.

Paladins don't need to be religious. Their power doesn't always come from a god.

Basically a Paladin makes the oath to be a slayer of evil or protector of innocence, etc, or such. The oath can be to a god, or to fey spirits, to nature, to ancestors, or just to themselves. The cause for taking the oath can be just wanting to be a hero, seeing injustice and needing to take a stand against it, being called to action by some divine or extraplanar entity, or for revenge against particular evil-doers. Their intention and oath is so strong it taps into divinity granting them powers : noting this is the generic divinity, part of the nature of multiverse and not necessarily from a god. 

This is also why their magic stat is Charisma : because the power comes from their self, their personality, their sense of conviction. It is the whole-of-being promise they make to themselves, a promise that becomes part of who they are.

Clerics get their powers, very specifically, from a God or similar divine being. Paladins are the source of their own power (even if unlocked by faith and service to a God, they remain their own source of power).

Also important to note the "justice" and "righteousness" is a perspective. A paladin can still be "evil", in some ways, by serving their tenets in a skewed perception way. A vengeance paladin may form their oath, say, because a goblin tribe killed their family so they have sworn vengeance against all goblins and will not stop until all goblins are dead - regardless of whether a goblin is good or evil, they are blamed for actions of others and are to be slain in the eyes of that paladin who will see this as "the good for world". Despite being objectively evil and genocidal, the paladin believes themselves righteous in their all-consuming vengeance that they gain power from it and see themselves as a good guy. 

Paladins don't necessarily serve gods. Some might. Many do. But you can be a paladin without gods - you can even be a paladin that is against the gods and actively trying to destroy them.

So, presuming that a Paladin is religious, and presuming that a Paladin is able to do so (because not all campaigns allow multiclass, and the way multiclass orks is not the same in all campaigns), i can say that there are indeed some multiclass paladins.

But also, what makes you think a traditional, Matter of France based Paladin needs to?

Charlemagne and Roland only ever stepped foot in a Church if they had to. THey were somewhat busy dealing with the masses and spreading the Word, otherwise.

Paksenarrion rarely set foot in a church. 

The now famous business card of the eponymous gunslinger never once mentions his stepping into a church to pray.  And the D&D Paladin grew out from a mash-up of Have Gun, Will Travel and the Matter of France with a sprinkling of the Matter of Britain.

Generally speaking, they aren't meant to be where a Temple is. THey are supposed to be where a temple is not.

Clerics are chosen by a deity. A paladin chooses their deity.

Quote from Zev_Oster >>

I know it's a dumb question, but I mean it. Paladins are often radicalized in their own oath by some religion, even if the direct cause of their beliefs is something more secular. For example, a paladin taking the Oath of Vengeance might worship Tyr. They clearly spend a lot of time at temple. So why does a Paladin become so ingrained in their religion and yet only defend its principles informally? 

 
Mechanically it’s because they’ve been divorcing classes from hard religious affiliations/requirements for a while. It used to be that Druids and Rangers had their own lists of proscriptions and could lose access to class features if they failed to keep to them. Those got dropped along the way since people wanted classes to be more free-form and have fewer hard restrictions on player agency. Heck, even Clerics can just represent a “concept” rather than have an actual discrete being involved.

Lore-wise, as has been said, the question posits a position that simply doesn’t exist. Plenty of people still play their paladins as “a paladin of X deity”, typically with their oath corresponding to one of that deity’s spheres of influence. An oath supplements their existing beliefs, it doesn’t supersede them. A Vengeance Paladin of Tyr goes out to bring evil-doers to justice in accord with Tyr’s teachings, to use your example.

Quote from Zev_Oster >>

I know it's a dumb question, but I mean it. Paladins are often radicalized in their own oath by some religion, even if the direct cause of their beliefs is something more secular. For example, a paladin taking the Oath of Vengeance might worship Tyr. They clearly spend a lot of time at temple. So why does a Paladin become so ingrained in their religion and yet only defend its principles informally? 

 You say this as if Paladins were presented to be as secular as a fighter or rogue. Paladins are explicitly holy warriors, 5e generification aside.

You don't need to MC cleric to be religious. You don't need to MC warlock if you make a deal with a powerful entity. Just because a class highlights a particular trait doesn't mean it has a monopoly on that trait. Roleplaying choices don't require multiclassing because those choices can be made independent of your class. You multiclass if you want the mechanics of another class; flavor is free.

From a mechanic perspective, it's because they don't synergize well and are very MAD.  I actually think a paladin cleric would be fine if you didn't need 13s in wisdom, strength, and charisma.  They'll also want a high constitution. A paladin would have higher level spells slots for smites doing this so it might be worth it.

Monk you'd also need 13 Dex thrown in there in addition to everything needed for cleric. You can't smite on unarmed attacks, don't need the unarmored defense, and generally I don't really understand what the paladin would want from Monk.  

Quote from Zev_Oster >>

I didn't phrase that right. Let me rephrase: what is a paladin's relation to the church?

 Whatever the player and DM decide it should be. The DM will set boundaries in their world about how pallys work. Then the player will decide where their character falls within that framework. Or sometimes outside of that framework, because PCs are special. 

Quote from Zev_Oster >>

I didn't phrase that right. Let me rephrase: what is a paladin's relation to the church?

Entirely dependent on the setting.

Paladins are originally based, as I noted above, on a blend of Charlemagne and his Knights with the fictional TV character Paladin. Charlemagne, from the Matter of France, was the King of the Holy Roman Empire who took it upon himself (and his retainers) to convert the heathens of Europe from whatever they had been worshipping to Christianity.  In game terms, he was bringing the word of his Deity to the people and encouraging them to follow that power. He was not part of a the church, he just really believed in it a lot. At the time the class was created, there was some conflation of the Matter of Britain with the Matter of France, so a tiny bit of Arthurian stuff got sprinkled in there as well. So, generally speaking, the Paladin has no connection to the church. The church is meaningless, except as a place they might go to pray or to donate stuff they find, if there is one nearby. Paladins are simply the separately chosen warrior of God, and they can be anything from a Sheepfarmer's daughter to a wild west gunslinger.

Clerics, on the other hand, are based on a very different model from Charlemagne -- they were meant to be more built along the lines of Alcuin, Friar Tuck, the Conquistadores, Moses, Bishop Odo, those who sought new lands in the name of God. They are Priests who seek to battle the forces of evil in any form that their deity so says, and to convert the heathen to the proper ways.  Odo influenced the "blunt weapons only" rule that applied in earlier editions, Alcuin enabled the wearing of armor and "pretty good with fighting", Moses brought the magic powers (as did Noah), Tuck was the source for the "companion and healing" part (though Alcuin also did the healing).

It has been D&D itself that has made it harder to distinguish between the two classes and their original models -- but beneath it all, you have folks who dedicate themselves to the Gods (Clerics) and Gods who picked someone to be a champion for them (Paladins).

* = The Matters are the story cycles. The Matter of France is all the French chivalry stuff, the matter of Britain is all the English chivalry stuff. Both features Knights, Kings, magic swords, and mounted riding as well as a code of chivalry.

Eh, being called to the task hasn’t been a Paladin element in a long time, at least as an explicit core aspect of the class. I’d say it’s more that Clerics are more focused on forging a spiritual connection with their deity to understand the whole of their will and teachings, while Paladins dedicate themselves to a particular aspect of the deity’s sphere and strive to improve themselves to better emulate that ideal.

Quote from The_Ace_of_Rogues >>

Eh, being called to the task hasn’t been a Paladin element in a long time, at least as an explicit core aspect of the class. I’d say it’s more that Clerics are more focused on forging a spiritual connection with their deity to understand the whole of their will and teachings, while Paladins dedicate themselves to a particular aspect of the deity’s sphere and strive to improve themselves to better emulate that ideal.

 I don't disagree.

I was focused more on the origins of the classes.

The present 5e Paladin has zero relationship -- they draw everything from the code they use. The only time they get popped into a religious thing is if their code does.

THis shifts 5e Paladins more towards the Matter of Britain -- knights who have powers to serve and to save, akin to the Arthurian stuff it draws from (which is better known than french stuff in the US) -- and towards the Code. It enables the presence of other codes, as well, expanding the class concept to include Bushido, for example, or Buddhist tenets of detachment, and so forth.

Which is, oddly enough, in keeping with the gunslinger from Have Gun, Will Travel that inspired the original class concept, lol. He had a code he lived by, and that code was based on Chivalry.

Eh, the 5e class is still pretty well tied to the concept of worship and organized religion; several class features involve the word “divine” and there’s still some higher power overseeing how they act in accordance with their oath. It just doesn’t outright ask you to pick a deity, and Clerics are essentially in the same boat there since technically they only need to commit to a domain. There’s just a fairly artificial degree of separation in both cases in the name of not “locking people in” to making their divinely powered characters directly tied to gods or organized religion.