In literature, a red herring is an informal fallacy that typically uses extraneous or irrelevant information to mislead the audience. It's used to give an astute reader several challenges during the telling of the tale.
In other words, they're purposeful deceits the author employs to mislead the folks who read their stories.
Red herrings are actually dried fish that are kippered, or salted and smoked, which turns their meat a reddish color. In 1807, a writer named William Corbett wrote about using red herrings dragged along the ground to train hunting dogs. This wasn't actually true, but the readers didn't know and the concept of red herrings was born.
Red herrings are used extensively in mysteries and thrillers, and are a staple for noir detective stories. By employing these misdirections, the author can attempt to get the readers to believe something is the correct answer when it is not. The concept is to include little tidbits of irrelevant yet related information that helps to push the reader into thinking a particular way.
Agatha Christie was a genius at employing red herrings. In Murder on the Orient Express, almost everything is a red herring pushing one away from focusing on the killer until you realize everyone was the killer. In her novel And Then There Were None, there's a list of how people are going to get bumped off. Victim number four doesn't seem to be a red herring until you realize that she told you flat out they were in the poem.
Employing red herrings should always be logical in some ways, but the information that incriminates should be irrelevant to the final solution to the mystery. Always give your readers the information that can dismiss the new clue somewhere in the text without making it obvious. For example, discovering the killer must have used their left hand to kill the victim might seem to clear a woman who always uses her right hand. But what if she was actually ambidextrous? Half the readers will wander off on the path that clears the woman, while the others might not be fooled by the accurate but not complete information. That's the fun behind reading a mystery!
So how do you incorporate red herrings into your work? I'm glad you asked. They should be blended into the overall information you give to your readers. If it's too straight-forward, the readers are distracted by the fumbling attempt to mislead them. Focus on giving the reader a reason to believe that something is the correct answer using information that is related yet does not factually implicate. Try reading some of the older mysteries such as Poirot, Miss Marple, and Perry Mason. You can even see them in old mysteries and detective shows on classic television.
A fascinating modern red herring example is Professor Snape in the Harry Potter series. He's constantly shown as a bad person throughout seven books until the last few chapters, where we finally learn that he has been trying to help Harry survive. All the red herrings are cleared up as we learn the truth, and the readers discover that the person they despised the most was the bravest person of all. That's why Snape and, by extension, actor Alan Rickman went from evil villain to beloved savior.