Do you want to use a standard paladin backstory, or something a bit more unusual?  The "classic" paladin was such a ridiculously restricted and restrictive archetype that there really are only a few valid backgrounds for such characters, but over the editions the class has changed enough that a 4E paladin can be significantly different if you want to go that way.  The core (as in Jungian-grade) archetypes basically boil down to:<br/><br/>The Knight-Errant (A knight on a holy quest, usually with limited information so that they end up exploring a lot.  Think Lancelot searching for the Holy Grail.)<br/>The Messianic Champion (A person who has been given a personal mandate by their god to sally forth and kick evil ass.  Think Joan of Arc.)<br/>The Infallible Hero (A knight who is chivalrous, virtuous, and valorous to a fault.  Think Superman.)<br/>The Destined Hero (A knight who has been chosen, despite the odds/obvious questions about why more experienced and better candidates were overlooked, to rescue a princess or save the day.  Think Link.)<br/>The Crusader (A knight who exists exclusively to fight a seemingly hopeless battle against some great, usually undying evil.  Think Paragon-path Commander Shepard.)<br/><br/>A modern paladin seems to have far more variety in possible backstories, of course.  Even so, there's some variety in the classics; for example, you could be a Tragic Crusader (as in, one who knows they are destined to die without truly succeeding in their mission, but who fights on anyway) or even a Quixotic Crusader.  Your Knight-Errant could be a Penitent, who's taken on the mantle of the quest to try and cleanse himself of sins for which he's truly regretful, or simply an ambitious young Templar eager to prove himself to the order.  The only one who doesn't allow much wiggle room is the Infallible Hero--the classic Gygaxian vision of the paladin--though with the way some people played it, you'd think The Preacher was an acceptable variant...