Argthtjtr

To be clear at the outset, a red herring is not a species of herring nor a genetic oddity, like an albino sperm whale, but simply a herring that has been smoked. Many early references to “red herring” in matches found by a Google Books search focus on the commercial trade in red herring, or dwell on the differences between fresh (or white) herring, salted herring, pickled herring, and red herring. Others treat a red herring as a kind of embodiment of a very modest meal.

'Red herring' as a false trail

Previous answerers have noted the OED’s recent attribution of red herring in the sense of “false trail” to William Cobbett in a story published on February 14, 1807. But the Cobbett instance is at least 25 years later than two occurrences in Google Books search results where red herring has that same figurative sense. The first confirmed relevant match that a Google Books search finds is from a speech by Mr. Courtenay on March 20, 1782, reproduced in the section on “Simile” in The Beauties of the British Senate: Taken from the Debates of the Lords and Commons (1786):

Though I have not the honour of being one of those sagacious country gentlemen, who have so long vociferated for the American war, who have so long run on the red-herring scent of American taxation, before they found out there was no game on foot ; they who, like their prototype, Don Quixote, have mistaken the barber’s bason for a golden helmet ; I now congratulate them on having at last recovered their senses, and found out their error.

Also relevant is this item from The Sportsman’s Dictionary; Or, The Gentleman’s Companion for Town and Country, Second Edition (1782):

But if it has happened that your exercise has been so easy so easy as not to sweat your horse thoroughly, then you ought to make a train scent of four mile in length, or thereabouts, and laying on your fleetest dogs, ride it briskly, and afterwards cool him in the field, and ride him home and order him as has been before directed.

A train scent, is the trailing of a dead cat or fox, (and in case of necessity a red herring) three or four miles, according as the rider shall please, and then laying the dogs on the scent.

It will be proper to keep two or three couple of the fleetest hounds that can possibly be procured, for this purpose.

The first edition of this book was published in 1778, but I haven’t been able to find a previewable version of it.

A match that is potentially even earlier, but is limited to a snippet view and therefore not fully confirmed, appears in The Universal Museum and Complete Magazine, volume 2 (1763, date not confirmed) [combined snippets]:

Lord G. It is right, however, that mankind should pursue it. It is productive of many good effects. The trumpet of fame rouses great minds to great actions.

Lord O. And to many bad ones too. Fame, you know, my Lord, has two trumpets. And though the pursuit of it may be good exercise for the general pack of mankind, and keep them in breath, it seems (to speak in my favourite language of a sportsman) to be only hunting a trail, to catch a red herring at last.

The reference to red herring here appears in the midst of a dialogue between the earls of Orford and Granville that other sources, including The London Chronicle, date to 1763, but without the "red herring" language anywhere to be found. Various snippet-view searches within the Universal Museum volume indicate that the probable date of the issue in question is June or July 1763—but the very presence of red herring in the Orford-Granville dialogue recorded there is mysterious, if not a red herring.

'Red herring' in the cause of sophistry

Another possible connection between “red herring” and false reasoning involves this first half of an anecdote from “The Spiritual Quixote,” in The Critical Review or Annals of Literature (1773):

A Roman Catholic Gentleman went a Partridge-shooting along with a Protestant neighbor of his on a fast-day : they were driven, about noon, by a thunder-storm, to a little public-house, where they could get nothing to eat but some bacon and eggs. The good Catholic had a tender conscience, and would eat nothing but eggs; the Protestant, his companion, who was one of your good sort of people, said, 'there could be no harm in his eating a bit of bacon with his eggs ; that bacon could not be called flesh ; that it was no more than a red-herring ; it is fish, as one may say.’ So the Catholic took a bit of bacon with his eggs.

'Red herring' as a practical-joke reward

Yet another possibility arises in the context of a memorable practical joke. From Gerard Langbaine, “Jasper Main,” in An Account of the English Dramatick Poets (1691):

He [Main] Died on the Sixth day of December, An. 1672, and was Buried in Christ-Church on the North-side of the Quire : having in his Will left several Bequests to Pious uses. As Fifty Pounds to the Re-building of St Pauls ; A Hundred Pounds to be distributed by the Two Vicars of Cassington and Porton, for the use of the Poor of these Parishes, with many other Legacies : amongst which I cannot forget One, which has frequently occasion’d Mirth at the relation. He had a Servant who had long liv’d with him, to whom he bequeath’d a Trunk , and in it Somewhat (as he said) that would make him Drink after his Death. The Doctor being dead the Trunk, was speedily visited by his Servant with mighty Expectation, where he found this promising Legacy to be nothing but a Red-Herring : So that it might be said of him [Main], that his propensity to innocent Raillery was so great, that it kept him Company even after Death.

The same story about Dr. Jasper Mayne, with the same punch line, appears almost a century later in William Owen & William Johnston, A New Biographical Dictionary, Containing an Historical and Critical Account of the Lives and Writings of the Most Eminent Persons in Every Nation, Particularly the British and Irish, From the Earliest Accounts of Time to the present Period (1784):

It is remarkable of this divine [Mayne], that, though very orthodox in his opinions, and severe in his manners, he was a most facetious and pleasant companion, and so wonderfully fond of joking, that he even contrived to do it after he was dead. Thus Langbaine, in his account of him, relates, that he had a servant, who had long lived with him ; to whom he bequeathed a trunk, “with something in it,” as he said, “which would make him drink after his death.” The doctor dying, the servant immediately paid a visit to the trunk ; but instead of a treasure, or at least a valuable legacy, which he expected, he found nothing at all but a red herring.

Similar accounts appear in John Noorthouck, An Historical and Classical Dictionary (1776) and in David Baker and Isaac Reed, Biographica Dramatica, Or, A Companion to the Playhouse (1782). Apparently, among the class of seventeenth- and eighteenth-century Englishmen who had servants, this tale of posthumously raising and then dashing a longtime servant’s hopes was simply too droll a joke to forget. In this case, a red herring is a disappointing reward in place of something that one has imagined and expected to be extremely valuable.

Conclusion

In all three cases (red herring as dog-training scent, red herring as consubstantiated bacon, and red herring as false prize at the end of long service), the fish can be seen as a metaphor for deception. Of the three, the dog-training scent red herring seems the likeliest to be the source of today’s term, but the practical joke red herring seems to have been around the longest, and it is not impossible that all three sources may have influenced today's general notion of a figurative red herring as something fundamentally misleading.

OP's question puts me in mind of Neither fish nor flesh, nor good red herring, which doesn't normally have anything to do with comestibles at all. It mostly just means not easily defined, and it's most commonly applied to people or opinions, not things which you might eat, or lay false trails with.

So far as I can tell, red herring has been a standard term since the year dot, when it originally meant exactly that (a smoked fish, red by virtue of the smoking treatment).

In the 1750's it began to be used figuratively to mean a meagre amount of humble food. Only much later was it used to mean a decoy.

The oft-repeated explanation of red herrings being used to deflect hounds sounds a little fanciful to me. Who would both happen to have a red herring around at the time, and wish to deflect the hounds? It sounds to me like an old-time American politician's attempt to sound 'folksy' by coming out with a neologism that would sound traditional, but be comprehensible on first hearing. On a par with out on a limb.

In his book, Salt: A World History, Mark Kurlansky says of New Englanders,

They also ate a great deal of salted herring, though they seem to have preferred lightly salted and smoked red herring, perhaps because of their limited salt supply. When these early settlers hunted, they would leave red herring along their trail because the strong smell would confuse wolves, [italics mine] which is the origin of the expression red herring, meaning "a false trail."

Let's look at three things mentioned above, namely: salt, fish and wolves. The early settlers were resolutely concerned with fishing and the production of salt. In Bradford's History of Plymouth Plantation we have an early letter to the Settlers at New Plymouth from Robert Cushman of England, who says,

We have now sent you, we hope, men and a means to accomplish three things, viz., fishing, salt-making, and boat-making: if you can master them your wants will be supplied. I pray you exert yourselves to do so.

These things were requested by Governor William Bradford of the Plymouth Colony. In Mourt's Relation: A Journal of the Pilgrims at Plymouth, we have an account of just how prevalent the wolves were near Plymouth, and their apparent fearlessness,

...John Goodman went abroad to use his lame feet, that were pitifully ill with the cold he had got, having a little spaniel with him. A little way from the plantation two great wolves ran after the dog; the dog ran to him and betwixt his legs for succor. He had nothing in his hand but took up a stick, and threw at one of them and hit him, and they presently ran both away, but came again; he got a pale-board [fence-stave] in his hand, and they sat both on their tails, grinning at him a good while, and went their way and left him.

Unfortunately, Kurlansky does not cite a reference to his etymology of the phrase. Nor do John Smith's Description of New England, Rev. Francis Higginson's New England's Plantation, William Bradford's History of the Plymouth Settlement, nor Mourt's Relation, all of which Kurlansky refers to, mention herring (or any other fish) in relation to wolves. That said, Kurlansky's etymology, in context, is simply a passing curiosity. And I find it at least plausible with the dearth of another suitable explanation.

Philoto didn't mention the following quote from Wiktionary.com, which is important:

Until 2008, the accepted etymology of the idiom was that red herring were used to train dogs to track scents. This has proven to be a false etymology.

This is backed by a study by Michael Quinon, which can be read here

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 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.

Later on, journalist William Cobbett

wrote a story, presumably fictional, in the issue of 14 February 1807 about how as a boy he had used a red herring as a decoy to deflect hounds chasing after a hare. He used the story as a metaphor to decry the press, which had allowed itself to be misled by false information about a supposed defeat of Napoleon;

Also, this was busted in an episode of MythBusters on Discovery channel. When the red herring was used as a scent, the hound stopped and ate the fish, but eventually went back on pursuit and located the fugitive.

There is an old rhyme:

The man in the wilderness asked me

How many strawberries grew in the sea.

I answered him, as I thought good,

As many as red herrings grew in the wood.

I always thought that this might be the origin of the phrase when used to mean a diversion or misdirection, but I suppose you would have to know which came first, the rhyme or the usage.

Just half watched a segment on how it's made over morning coffee about this.

I think it was in Finland that they use carved balsa wood models of herrings, painted red, to attract herring to their nets, like a duck decoy (I assume it was to the net, It was my FIRST coffee). Painting them red might well have been inspired by the smoked herring, but it would seem to me that red herring's ties top something false or contrived in the sense of a near decoy would more reasonably go back to that use.

Hunting lore. Centuries back when English lords (and ladies?) were tracking game (like hares and other animals) they were pursuing for the hunt. Rival “teams” would drag a red herring across the road to throw off the bloodhounds’ scent to gain advantage for their team.

The phrase has now come to be known as a way of distracting the opposition from a true course of action, etc.

Here's a reference I found in my ngram search for red herring.

In "Four letters to the Hon. John Stuart Wortley" by William Cobbett (1834), Cobbett appears to recount using the red herring as a cunning way to get back at Mr. George Bradley by leading their hunting party away from the hare they were hunting, away from the trail, and into a swamp. Cobbett relates the story of his youth to the Honorable John Stuart Wortley as an analogy to the willful deception that he claims is present in "A Brief Inquiry into the True Award of an Equitable Adjustment between the Nation and its Creditors", which Wortley had published earlier.

I'm not sure it's the first reference, but it's the first time I see the term used as an analogy.