They are one of the oldest types of stories. Who stole my lunch? asked the Neanderthal. Judging from the footprint in my favorite mud patch, I'm guessing it was Urm-Ough. Although Yert-Ragr has very similar feet...
Okay, so that's a dramatization. But mythologies are peppered with heroes who travel great distances to search for things: the answer to his great question, the deity who killed her family, or the one object that will let the owner live forever. You can boil almost any story down to a question, if you want.
But even if you keep mysteries to their definition-- start with a question, answer it by the end of the story-- mysteries are everywhere. They are probably the most prevalent style of subplot in fiction. In the mystery genre, a story is basically six or seven mysteries twined together. In a thriller, you have one mystery for half (who did it and how?) and the second half is dedicated to stopping bad things. In everything else, mysteries come and go as the author wishes. What does the Big Stick of Evil do, in an epic fantasy? How did the enemy hack into our weapon systems, in science fiction? Who is this mysterious woman from my boyfriend's past, in a romance? No story survives completely free of a mystery.
So how do you write a mystery plot line? Stick with the definition: start the story asking a question, finish by answering it.
But there's so much more to it than that, or else a mystery would last as long as a knock-knock joke. Mysteries have more than that to draw them out. Red herrings, false assumptions, sheer volume of clues-- expanding a mystery comes down to muddying the waters.
The easiest, most obvious way to build a mystery is to add clues. Clues, clues, clues— make the puzzle as complicated as possible so that even when the characters get the edge pieces down, the middle takes time. Except... a confusing mystery is, well, confusing. When it's finally explained, it might take more energy to understand than it ever took to find all the clues. If the audience can't understand it, they're going to lose interest.
So keep it simple. But how do you make it both complicated enough to take an entire novel to solve, and simple enough to be understandable once all the clues are laid bare? Introduce the clues in reverse.
Hello, I am Captain _____. Fill in the blank. It's easy to figure out when you see it all in its correct order. But how about this: Fill in the blank. ______ the enslave to wants Loki. Harder at first glance, right? How about scrambling up the clues? Fill in the blank. ______ name Stark's is middle Tony. It's much harder to answer a question when the hints come in reverse, or scrambled. (This is the entire premise of that one television contest thingy with the mysterious theme song. Google says that's Jeopardy.)
So, figure out the mystery, get a couple of clues together, and line them up for the characters to find in reverse. But even that could be guessed in a matter of minutes, with some good thought. You need to confuse a little more.
Red herrings are intimidating, but do not fear. They serve to distract from the real prey by leading the bloodhounds down the wrong trail. Despite seeming like big, fancy, etymologically complicated gimmicks, red herrings are simple. They're just another mystery.
Seriously. A red herring distracts by leading down a wrong trail-- all that means is there's another trail out there, which means another mystery. All you have to do is confuse the clue for one mystery with the clue for another.
Imagine someone steals my shield one day. Big, round, and shiny, you'd think I couldn't misplace it, but it's gone. In its place are the lonely crumbs of chocolate cake. I only left the shield behind for two hours between three and five, and only one person I know eats cake during that time. Thor must have taken it.
On the contrary, Thor was just coming to ask me what Tony was whistling so tunelessly, and put his cake down for a moment as he admired my current whittling project. The shield was already gone by the time he arrived.
Who stole my shield? That's mystery 1. Why are there chocolate crumbs there? That's mystery 2, and that one is easily solved-- but it's already served to throw me off track. That's a red herring, thanks to Thor.
The detective can assume a red herring is a clue to the main mystery, but they can also misunderstand real clues. Only Sherlock Holmes has ever completely resisted guessing at the mystery's solution before it's completely clear. What if Thor had been in my room, fighting off the shield thief with his chocolate cake? While that's certainly a clue to who might be in my room, I can still leap to the conclusion that Thor took my shield. While a clue might be really important to mystery 1, it can also be misunderstood by wanton theorizing.
The bigger you want your mystery to be, the more of a part you want it to play, the more mysteries you're going to have to introduce. This really isn't as bad as it sounds. You just withhold information from the reader for a little bit longer. Tie six or seven mystery plots together, and you have a mystery novel. Twine a couple around a grander plot line, and you have a nice accent for any type of story. Confuse as much as possible until the resolution; mix up and reverse your clues, add more mysteries for red herrings, and theorize wantonly when possible. All these things will help your mystery thrive, wherever it happens to appear.
P.S. Barton probably stole the shield. It makes a really good target.