All you need to start an agile project are two things: a vision and a backlog of things to build during the first few weeks. In many cases these things are represented as user stories. It is the product owner's (PO) or product manager's (PM) task to keep that backlog in order: Writing new user stories, prioritising and re-prioritising them and disposing of them when they become obsolete.
There's a number of ways to structure a backlog. A common one, that I'm currently using, is having sprint backlogs for the current and a few upcoming iterations, plus one big flat product backlog where all stories go that aren't scheduled for a particular sprint. Another one would be something called Story Maps. I haven't used them, but here's what I've learned about them during an OpenSpace session at the fabulous Agile Lean Europe 2011 Unconference in Berlin (and in a little bit of reading, particularly Jeff Pattons blog post about it).

Everything starts with the vision, it lets you set your goals, the first order structure of your project. Each goal is usually associated with a number of personas – fictive prototypical users of the functionalities. For each persona you will find a number of things they will want to or have to do. A management summary of each of these things will go into what is often called an epic user story (or just epic).
What's described in an epic is usually way too big to be estimated and implemented. Suppose one of your personas, Helmut, a photographer, needs to edit his photos after upload to your service. Here's your epic. It needs to be broken down into User Stories that adhere to the INVEST criteria, which stands for Independent, Negotiable, Valuable, Estimatable, Small, Testable.
But before you start writing those user stories, think of the individual features needed to make up your epic's functionality. Maybe the photographer needs to do color correction, shape the image (rotate, crop, resize), and so on. Once you think you've found them all the time has finally come to write the user stories.
Thanks to the structure in place by this time, it should be fairly easy to come up with the stories needed to build the features of your epic. While the “brain-storming” approach I've been using so far fails to give any hints on whether your set of stories is complete or not the fine-grained separation at feature-level should make any omissions obvious.
In order to further support this, and to also come up with a sensible priority order, stories in story maps are each assigned one of three levels of importance: Walking Skelton, For Go-Live, and Wow!
Assign a story the Walking Skeleton label if you think it is needed to get the most basic implementation of the feature you can think of to work. _For Go-Live _means: without this story I wouldn't bother to release this feature to any customers. Last there's Wow! – these stories will please your customers and, possibly, give your service an edge over the competition. Probably some of these will never be implemented because their priority is too low and you decide to ship your new functionality without them.
This brings me to a couple of questions that I will have to leave open for further investigation, and a few more that were raised during a workshop day yesterday at Liip: Should I dispose of an epic only when it is completely implemented? Should I drop any Wow! stories in it once I decide to ship it before they're implemented? Or would it make sense to keep them in a backlog, along with the epic to which they belong (even though that's been mostly implemented)? Or should I create a new epic (e. g. “Improved Image Manipulation”) and assign my leftover stories to it—and would they belong to the Walking Skeleton of that new epic? Should stories from different epics be done in the same sprint, and how will we prioritise them? And last, but not least: How do we do this practically with our customers, especially in ongoing projects?
We're going to elaborate on these questions during the next few weeks. Please share your thoughts if you're already using Story Maps.