I was about to write something up myself about how they're born out of the massacre of the Roncevaux Pass through the Song of Roland - but you can just go and read some things on the wiki:

Song of Roland

Paladins