Blue Fire five times. The plot changed constantly, the story never did. To use my house analogy: You build a house once, but you redecorate it every year.
The house is story. Decorating is plot.
Some key things to remember when plotting:
1. The goal of plot is to illustrate your story
If your story is about a soldier trying to save his king, then the plot is going to be the steps in which that soldier takes to save his king. Subplots will naturally arise, but even they will illustrate some aspect that ties back to that main storyline. That core conflict or story problem.
I often suggest writing down that one sentence that says what your story is about and taping it to your monitor to remind yourself what the end goal is. When you think up a scene, look at that sentence and ask yourself how it connects to that. It can be subtle, it can be an intermediate step to a bigger goal, but it'll be something that has to happen in order for the core conflict to be resolved. If there's no connection to the main goal, odds are the scene can go. It's not advancing your story.
One thing to keep in mind though, is that it doesn't have to be a direct line connection. If the story goal is to break the king out of prison, all kinds of things can go wrong when trying to break him out. Those smaller obstacles create plot, because they all make it harder for the hero to achieve his goal. The end goal is still the same and that end goal (freeing the king) is what's critical to the story.
2. Never let the plot dictate your story
It can guide it, influence it, enhance it, but it's easy to write a scene that's really cool, but not right for the story. And since you love that scene, you bend over backward to try to make it fit. If you're forcing it, it's not working, no matter how cool or how well written the scene may be. Cut it, save it in another file, but don't let it waylay your story.
Say, for example, while trying to free the king, the hero discovers the warden is corrupt and planning to kill a bunch of wrongly imprisoned political prisoners captured when the king was captured. This is a bad thing, but it has nothing to do with the story goal of saving the king. It might work as a nice inner conflict (the hero has to choose between abandoning the prisoner and saving his king), but to go and actually try to save those prisoners is very likely going to waylay your story and send the plot off on a tangent. Will that scene be cool? Probably. Will it have stakes and goals and everything it needs? Sure. Does it advance the story? Probably not.
Why? Because the stakes don't escalate, and it's basically the same goal with smaller stakes. Saving prisoners he doesn't know or care about is a lot less important that saving the king he adores who is needed by the people.
And that's the tricky part, because it really seems like it should be a great subplot, right? But those prisoners aren't keeping the hero from anything. They're a sad situation to be sure, but leaving them there isn't going to affect his goal of saving the king at all. He doesn't have to free them to free the king. He might want to, might be haunted by it because he didn't, but it's not a plot-advancing goal. It's a delaying goal. It's stuff to delay your hero from achieving his goal instead of something designed to make it harder and raise the stakes of that goal.
However, if you find yourself in a situation like this, where you write something unexpected that looks cool, you can start thinking about ways in which saving those prisoners does directly affect saving the king or a bigger story goal. Maybe the king needs to be the one to save them to gain supporters. Maybe it turns out later one of those prisoners is important to the cause or the king in some way. Instead of sending your hero right at it, it might be a nifty seed to plant that will later be exactly the right problem for the plot.
3. Characters create the plot
Since stories are about characters, characters act and create plot, which in turn illustrates a story. So, characters are where your plot is going to come from. What they do is what's driving your story. They're going to want things, want to avoid thing, want to cover things up. They're not just going to sit there and do nothing. They're going to act in some way. This is a biggie, so I'm going to go into more detail on this over the next few days. It deserves its own post.
4. Plot needs stakes
It's probably more accurate to say characters need stakes, but if there's nothing to lose, the plot won't matter. Something to lose is probably more important that something to gain, crazy as that sounds. It's the struggle that makes the story compelling, the risk that things might go wrong and the hero will fail and have bad stuff happen to them.
Why someone acts is a huge driving force behind plot, and stakes are a big part of that. It's what turns a bunch of scenes into a story, because the events suddenly matter and aren't just characters acting out a script. This also deserves its own post, since characters and stakes are key to a good plot.
Plotting can be challenging because there really is no limit to what you can do. But if you keep your core conflict in mind, it makes it a lot easier to identify what advances your story and what's just more plot.