I suspect Trey Parker and Matt Stone used real-life experiences of "anti-ginger" sentiment as the basis of their show. I've read that anti-redhead sentiment in England dates back at least a couple centuries, where Celtic descendants from Ireland and Scotland were considered members of an "inferior race" by the Anglo-Saxons.
Then again some of the most famous English people have been redheads. Elizabeth I and Henry VIII, for instance.
I really don't get the dislike at all. It seems to me that the dislike of redheaded people's appearance has more to do with other factors that tend to go along with red hair. Pale complexions as a general rule aren't as attractive in 'western' culture as a bronzed skin, whether naturally through ethnicity or with help from the sun or a tanning bed. Many (most?) redheads don't tan well or can't tan at all hence they're naturally paler and therefore less attractive.
Perfectly clear complexions are also considered the pinnacle of beauty, while many redheads have freckles and lentigines ("liver spots") dotting their skin.
I think I like redheaded women precisely because they're unusual.
I reckon that the anti-red head mania dates from the Highlander wars in Scotland and England. The highlanders were red headed scots and the only threat to the english greater than the French or foreign invasion, they unleashed sectarian intrigue and war across the whole of the british isles and then imperial wars abroad to try and neutralise it, the prejudices and ancestoral memories probably linger on.