The story
Carolina dogs were called yellow dogs because many had yellow coats. The fact that many mongrel dogs also had yellow coats lead to the term's application to any worthless item or person. For the etymology of the term Yellow Dog Democrat, see that entry.
Etymology from Wiktionary, CC BY-SA 4.0.