A red herring is something that appears to be a clue but in fact is not. Just as smoked herrings were used to lead fox hounds on a merry chase, red herrings give mystery readers false trails to follow.
Some of the more common varieties of red herrings follow. Depending on the length and style of your story, you can mix and match them to your heart's content.
One way to introduce characters as red herrings it to give them all motives. In many classic puzzle mysteries, nearly every person encountered benefitted in some way from the crime.
Another way is to provide characters with means and opportunity. If a person seems capable of committing a crime but no motive, two possibilities are created. Either the person has a motive yet uncovered or the person is working in concert with someone brimming with motive.
Readers have become so accustomed to these approaches that they sometimes assume any character in the story is a suspect because why else would the character appear? This leads to the person-least-likely syndrome and other assumptions that you can use to your advantage.
The first thing many people think of when setting is discussed is place and there are two ways that place can create red herrings.
Characters may refer to places in passing or as part of an alibi. What's the significance to the place? What might an investigator learn by visiting the site? The reader will wonder.
The investigator may actually visit the site. When that happens, you get to choose which opportunities for further investigation will be red herrings.
A general description of place may also generate avenues for misdirection. Make the reader question the significance of the crime being committed in an urban (or suburban or rural or wild or waterfront) area. Which people would be most comfortable acting in the environment you've chosen?
Setting does mean more than place and you can use the other aspects of setting to influence how your reader responds.
Is the time of day the event occurred significant? Someone is shot exactly at noon. Was is coincidence or something more?
Is the day of the week significant? A bank robbed on a Tuesday raises questions when the drawers would normally have been light but this week was an exception. Who had inside information?
Is the time of year significant? Serial crimes that occur during the first week of school vacations may be committed by someone who works in education or has children who couldn't travel while school was in session.
Is the weather significant? Does a particular character appear more likely to be involved if the crime occurs on a hot day versus a rainy day versus a day when the area is blanketed in three feet of snow?
Make every detail you include work on multiple levels.
There are two categories of objects that you can add to your descriptions: objects that appear and objects that don't appear.
What does your investigator see at the crime scene? It is not uncommon for writers to catalog the evidence. You get to decide which items are present for verisimilitude, which items are present as genuine leads, and which items are present as red herrings.
The same question can be asked wherever the investigation takes your main character.
What doesn't your investigator see? A more subtle clue is not what appears at the scene but what might be expected to but doesn't. Who could have easily removed the item and had the motivation to do so?
Whatever the category of object, there are shades of obliqueness. Compare the following three objects which might be left at an arson site: an axe, a bag which could be used to transport an axe, and a whetstone suitable for sharpening an axe. How about traces of an oil commonly used by woodcutters?
An effective way to trick readers is to introduce objects with more than one explanation. Does a pile of cigarette butts mean a long wait or a short dump of an ashtray? Peanuts are not out of place in the victim's apartment unless it is later revealed the character was allergic. Do the peanuts implicate the killer or introduce the existence of an unknown visitor?
The greater the number of ways a reader can interpret a specific item, the likelier the chance that your reader will make a wrong assumption.
Nothing should be placed in the story simply to mislead the reader. If you're going to leave a scalpel under the couch to falsely implicate the surgeon, you need to have an explanation for why the scalpel was found in that location.
Too many red herrings can frustrate the reader, especially if every clue seems to point at a different character. When matching wits with a reader, you need to remember that readers come to the genre for an entertaining game.
Non-puzzle mysteries also use red herrings. There will be fewer and their purpose will be slightly different. Instead of making the reader incorrectly guess what happened, they make the reader incorrectly guess what is going to happen.
There is a difference between misleading the investigator and misleading the reader. Readers watch Sherlock Holmes follow logical (and apparently logical) trails. Readers are riveted by investigators who don't know something the reader does, especially if the knowledge could lead to a crisis situation.
If you send the investigator down the wrong trail and have set things up so that the reader is likely to follow, don't belittle the investigator for the mistake because you're insulting your reader as well.
Study classic puzzle mysteries by writers such as Agatha Christie. Examine the way she drops clues (and red herrings) throughout the story.
How were you, as a reader, misled?