Long before it meant a false clue, a red herring was simply food. Herring that had been heavily salted and smoked turned a reddish brown and kept for months, which made it a cheap staple and a strong-smelling one.
The explanation you will find almost everywhere is that hunters dragged red herrings across a trail to throw hounds off the scent, either to train them or to sabotage a hunt. It is a satisfying story. It is also, as far as anyone can tell, not what happened.
Red herrings did have a place in hunting, but as bait for a trail rather than a decoy. In 1599 Thomas Nashe wrote that for drawing hounds to a scent, nothing compared with a red herring skin.
The etymologist Gerald Cohen and the researcher Robert Scott Ross traced the rest. Their findings appeared in 2008, and the Oxford English Dictionary accepted them. The key text is a 1697 horsemanship manual by Gerard Langbaine. It advised training horses by dragging a dead cat or fox to lay a trail for hounds, with a red herring as a substitute. Nothing in it describes using the fish to mislead dogs.
Cohen, Ross and the OED credit the figurative sense to William Cobbett, a combative English journalist. On 14 February 1807, in his Weekly Political Register, Cobbett told a story of using a red herring as a boy to pull hounds away from a hare. He used it as a parable: the London press, he argued, had been fooled by a false report of Napoleon's defeat and had chased the wrong scent. The story was very likely invented to make the point, and Cobbett returned to it in 1833.
Cobbett was not quite the first, though. Wikipedia quotes a 1682 pamphlet that already mocks a red herring "hunted and trail'd through the Kingdom, to make a noise." Wordorigins.org cites similar political uses from the same year. Cobbett popularized the image; he did not invent it.
From there, "red herring" came to mean any distraction from the real issue. Mystery writers made it famous as the planted clue that points to the wrong suspect, and logicians adopted it for an argument that changes the subject.
So the phrase is doubly misleading. The fish was real, the hunting practice probably wasn't, and the origin story most people repeat is itself a red herring.