I have to thank Tim Haines for turning me on to RSpec not long ago via his LinkBuddy facebook application. I've been trying to suck in as much information as possible about this intriguing tool. Imagine being able to describe your stories AND their corresponding acceptance criteria in code, and then being able to execute those tests to demonstrate that functionality is complete.
Pat Maddox created a screencast that talks about this tool, as well as Story Runner. The screencast is rather lengthy (35 minutes, 102megs) but it is worth its weight in gold. Whether you are looking to learn more about this tool, or whether you are simply looking to gain more information into what constitutes a complete story, this screencast is absolutely recommended.
The tool is specific to Ruby, however the concepts can be applied broadly to any sort of agile development. Structuring an effective story is probably the biggest hurdle to successful agile implementation.