A civilization of cat-people rose and fell on Red Dwarf in the 3,000,000 years between its leaving Earth and the time the radiation reached a low enough level that Lister could safely be let out of stasis. Like most civilizations, this one had its own religion and the episode Waiting for God gives quite a strong message on religion in general. Just stuff to think about.
The supreme deity in their religion is Cloister. Legend has it that Cloister was frozen in time to save Frankenstein, the Holy Mother of the cat-people. He would eventually return and lead the cat-people to Fushal (I always thought it was spelled Fyushal in Infinity Welcomes Careful Drivers but resiak (user) swears it's Fushal in the Official Programme Guide, so I use this latter spelling), the Promised Land. After arriving at Fushal, the cats will be able to partake of all manner of hotdog and donut and they would wear hats of great majesty, though they be made of colored cardboard and have humorous arrows through the top. At least, that's what legend says. This is actually their interpretation of Lister's plan to open a hotdog and donut diner stand on Fiji, but three million years of retelling the tale warped the names and events beyond recognition.
Most of the cats on Red Dwarf died in Holy Wars fought between the two factions -- those who thought the hats should be red and those who thought the hats should be blue. Daft, especially since, according to Lister, they were supposed to be green. The cats not killed in Holy Wars built two arks, one for red-hats and one for blue-hats, and they left Red Dwarf in search of Fushal. They used a star chart Cloister supposedly left for Frankenstein. The sacred writings read "Seven socks. One shirt." Unfortunately, Lister had lined Frankenstein's basket with his laundry list. So one ark crashed into a comet, and the other flew onward forever.
Lister was most disturbed, though, when he learned they actually made things up about him. He was supposed to have given them Five Sacred Laws (not quite the Pentabarf but just as loony), one of which is "It is a sin to be cool." Of these five, Lister claimed to have broken four of them, and would have broken the fifth but there are no sheep on board.
When Lister emerged from stasis, all the cats were gone except for two. When the arks left Red Dwarf, they left the sick and the lame to die. Of the sick and lame, there was a cripple (Cat's mother) and an idiot (Cat's father, who later chewed off his own foot). There was no trace of them by the time Lister emerged from his 3,000,000 year stint in non-existence. Only Cat and a blind-old priest who'd lost his faith. Lister was able to restore the old man's faith by pretending to be Cloister and promising him A+ status on Fushal, where he'd get his own room and patio and barbecue grill. He performed a "miracle" by restoring his hat (Cat put it on instead of burning it like the old man asked), and the old priest exclaimed "This is the happiest day of my li--" and then fell over dead.
Lister was upset at finding out the cat-people used religion as an excuse for them to be extremely crappy to each other, and I'm sure there is a moral in here somewhere. | 
