Ah, I never really thought there was a difference between the two.  I most likely screwed up there.

It is a very fine distinction which a lot of pople don't make, but it's still there.

Think of the plot as a skeleton for a story, or a path down which the story walks. The story is what you experience. The plot is merely what happens.

Hm, that didn't make a lot of sense. Give me time to come up with something better.

Who cares? Stories are for Movies, TV's, and Books.

I don't need a storyline for my games.

I think you're onto something there.

Plot is definitely the skeleton. I like to think of plot as how you would describe/summarize the story to another person. For example: Lord of the Rings is about two hobbits who are on a journey to destroy a magic ring that could fall into the wrong hands. Star Wars is about a farmboy who gets caught up in a rebellion to free the galaxy from an oppressive empire. Romeo and Juliet is about two lovers, but their families hate one another.

Plot is the story boiled down to its most basic elements.

Story is everything else. All the specific details, the characters and their interactions, the symbolism, the themes, etc. The story is the full package.

... though that's not any clearer than what you just said.

@zerosaurus

"Who cares? Stories are for Movies, TV's, and Books.

I don't need a storyline for my games."

Yeah! Screw trying to expect more out of games.

I don't think all games need an amazing storyline to be good, but as games increasingly use narrative as an impetus for gameplay, I think we need to expect more out of the types of stories in games and how they are told.

Yes, they do. While I thoroughly enjoyed Twilight Princess and Super Mario Galaxy, the story in each, particularly Super Mario Galaxy, made me feel like a retarded 6 year old. Made an otherwise pleasurable experience excruciatingly painful.

 You're out of time.

Seriously though, the difference is huge. Yes, bigger than 2,038,582 (anybody get the referance?).

All games have a plot, and it's pretty much equal.

Zelda:

The Princess is kidnapped and the kingdom of Hyrule is under attack by an evil person's minions. The hero needs to kill the evil person.

Fire Emblem: PoR

Daein is attacked by enemy forces. To save their country, the group of heroes needs to drive the enemy forces out of the land, and kill the enemy leaders to make sure it doesn't happen again.

Super Mario

Princess is kidnapped, Mushroom Kingdom is under attack by evil minions of Bowser. Defeat the minions and then Bowser to bring peace back.

But those games do by no means have the same story. There's an enourmous difference between them.

I kinda went away from my own point there:

Story and plot is completely different. 

It's obvious what story is, but what plot really is, is this.

Plot: What you need to know to sit down and play the game/watch the movie.

I think the Zelda stories are cliche, but they're meant to be. It's pretty much the Zelda tradition lol

Zelda , like mario didnt have any deep storyline just some cliche "You gotta save the princess from the evil forces" that kind

I'm not very good with semantics, but to me the plot is general what happens and why. A story is that, and everything else that comes with it.

A cliched plotline doesn't mean a bad story, or even a cliched story really. Look at Pixar movies, most of their movie's plotlines are fairly cliched. When you watch something like Toy Story, you'll likely know the general plot progression and the kind of ending the movie will eventually reach. It's the classic homeward bound kind of plot with a pair of reluctant friends, and Toy Story doesn't do anything to significantly change that kind of plotline. What you won't likely know how Buzz reacts to finding out he's a toy, or what to expect from Sid's "experiments", or how Woody eventually stops Sid, or every little joke and adventure along the way.

Basically the devil is in the details. Pixar's CEO John Lasseter is a big Hayao Miyazaki fan. A decent amount of Miyazaki films have very simple storylines. Something like My neighbor Totoro's plotline could be easily described as two girls befriend a demon. The details are what make it a joy to watch.

I've enjoyed every Zelda game I've played so the stories in my case aren't bad. There are cliche's in every games story pretty much so its a moot point to me.