Stories are the fuel for your agile engine. Your team takes them as input and transforms them into business value. If your stories are lacking, it can really wreak havoc on your engine and your results.
Bill Wake came up with a clever acronym for good stories. Good stories meet the INVEST criteria. They are independent, negotiable, valuable, estimatable, small and testable. Below is my take on these (see http://xp123.com/articles/invest-in-good-stories-and-smart-tasks/ for his original blog entry).
Stories should be independent of each other (as much as possible). I.e., they should be doable regardless of whether other stories are done. This enables the product owner to more easily prioritize based on business value. It also greatly simplifies your backlog.
Stories should be negotiable. They shouldn't start off as having every possible detail explicity defined. Don't go into more detail than you absolutely need now. Going into too much detail too early can result in wasted work if the story doesn't get done. If the story does get done, premature work becomes stale. Things change and it needs to be reworked. Worse, going into too much detail prematurely can cause you to overly constrain your solution. Potentially ignoring solutions that would add more value and/or less cost.
It should be clear what is the value in doing a story. Why is this valuable? How valuable is it relative to other stories? Naming plays a big part here. Focus the story around what the user gets out of it, not how it gets implemented. This helps prioritization / focusing on the most valuable items first.
Stories should be estimatable. You should be able to put a relative size on a story. If you can't, it either needs to be better defined or split into smaller stories. Sizing is another factor in prioritization. Having value and size enables you to compare return on investment.
Stories should be small. This one has been revised by some to say that stories should be the right size. Stories that are far out can be fairly big / a place holder. Breaking stories down prematurely can make it much more difficult to maintain you backlog. Stories that are going to be done in the next couple of weeks should be small. On the order of 1-3 days or so. Keeping it small helps to increase focus. It also tightens the feedback loop and helps to keep less work in progress. Get it done and accepted. Move on to the next one.
Finally, stories should be testable. You should know what it will take to consider them done. Creating acceptance criteria can be a great way to make this clear. Don't leave iteration planning without agreeing on these for each story.