The answer I've always known and the one supported by a History Channel program I love: Worst Jobs in History.
In the 1997 edition of Facts on File Encyclopedia of Word and Phrase Origins, Robert Hendrickson firmly asserts that “Escaping criminals in the 17th century would drag strong-smelling red herring across a trail to make pursuing blood-hounds lose the scent”. Brewer’s Dictionary of Phrase and Fable, and many dictionaries, say that red herrings were used to confuse the hounds chasing a fox.
The OED’s current entry for the figurative sense of red herring points to a reference in Nicholas Cox’s The Gentleman’s Recreation of around 1697 (Mr Ross says it was actually in a treatise by Gerland Langbaine on horsemanship that was bound into the third edition of this work without attribution) that appeared to suggest that hounds were trained to follow a scent by trailing a red herring on the ground.
This was a misunderstanding, as Langbaine included it in a section on training horses so that they became accustomed to following the hounds amid the noise and bustle of a fox hunt. He suggested a dead cat or fox should be dragged as a training-scent for the hounds, so that the horses could follow them.
If you had no acceptably ripe dead animals handy, he added, you could as a last resort use a red herring. Neither the original misunderstanding of the text or the correction suggests why red herrings might be thought of as laying a false scent to draw hounds off a trail, quite the reverse.
Eh, it all boils down to the same thing: to throw off the scent. To confuse the issue.