A common misconception is that agile doesn't scale to large and/or distributed teams. Many of the agile methodologies focus on smaller teams, but that doesn't mean that their usefulness is limited to that context.
Large, distributed teams present their own challenges. These situations can be more difficult in any project management approach (including waterfall). Agile has proven to be compatible (I would argue superior) with these scenarios.
To start off, the teams should do release planning together. Key members should be flown in so that critical mass is achieved at a single location. This is the most important time to get everyone together. The goal is to supercharge the planning process.
An approach that has worked well is to have release planning last a week. The first four days are for discussions of the backlog. How to approach things, how to distribute the work, etc. The final day is about laying out the iterations and getting a feel for what the release is going to accomplish. Important note: this is not a commitment, this is a projection which will be updated every iteration based on new information.
Each iteration should be coordinated between teams. This can involve discussions before and after planning to synch up. It can also involve teams sending representatives to other teams' meetings. Rather than doing things in sequence (Team A does their part in iteration 1, Team B in iteration 2, etc.), try as much as possible to break things down so that each iteration produces additional user value. Also important is that the iteration should stand on its own (i.e., if you stopped work on the feature after the iteration, nothing would be wasted).
Scrum has a concept called a scrum of scrums. This is taking the daily stand up meeting (where you answer what you did yesterday, what you're doing today and what is blocking you) and doing it at a meta level. Instead of each individual representing themselves, each individual represents a team. Every team participating in the coordinated release should have a representative.
Two critical success factors to this. First, you have to keep the meeting short (ideally under 10 minutes). This means sticking to just the points that are relevant to the other teams (i.e., what work are you doing that is most likely to affect them). The second critical success factor is that blocking items need to be taken seriously. The goal is to get them resolved by the following day (i.e., given priority). If they're not, they should be brought up again and again (until they're resolved). This focus on resolving dependencies quickly can make a huge difference.
Another thing that can bring teams together is to have one demo (involving all teams) rather than several smaller ones. This keeps the teams aware of what is going on with the larger effort.
At the end of the release, all teams should participate in a retrospective to identify what went well, what went poorly and how things should be done differently. This ensures that you're continually improving things and tweaking them to what works best for your teams.

“Also important is that the
“Also important is that the iteration should stand on its own (i.e., if you stopped work on the feature after the iteration, nothing would be wasted).”
How do you stay releasable after each iteration and what does it mean to be releasable?!? Grappling with this question seems to be the biggest hurdle for many people trying to move to Agile. Questions like: “This feature will take two months to complete. How do I stay releasable?” or “Does releasable mean we can show customers a partial feature to get feedback or does it mean we can ship it to the market and it adds value?”
I had a conversation with Roger Cauvin (http://cauvin.blogspot.com/) about this topic recently. It seems opinions vary. I would like to hear your views on this. Maybe a topic for a blog entry?
My opinion is here. It
My opinion is here.
It coincides with Alistair Cockburn's view:
"For agile development to work, each person's activity must be visibly linked to delivering value to consumers. Our trade has become fixated on shortening the length of an iteration to score higher on the agile machismo scale. The consequence is that the programming team works increasingly in isolation from the realities of delivering working, useful software to users and stakeholders."
Now, what does Cockburn mean by "delivering software to user and stakeholders"?
"The repair is simple: connect every activity to a release or delivery to real users (delivering to even one real user makes a difference). Evaluate the team's work based on how often they deliver to real users and how long it takes a new requirement to reach the users. Replace the fuss around iterations with fuss around deliveries."
To Cockburn, the important thing isn't an actual release, but delivery to one or more users, so that you are linking your efforts to real stakeholder value, and so that you can get user feedback on a regular and frequent basis.
What is a story
Lots of good points in your comments.
To me, how you break things up into stories is key. For example, you could break it up into design, implement database changes, implement back end and implement front end. I would not recommend it though. Because if you did it that way, the earlier stories provide no user value until you have the last story. If you don't do the last story, you've got dead code (which cost you to develop and will cost you to maintain). Similarly, you don't want to do things like add widgets for future use. You might never get back to it.
Alternatively you could approach it so that the first story was to do the most simplest aspect of it. Then the second was to add on another capability (maybe refactoring a bit), etc. In that way, you could stop at any time. Some customer value has been added (maybe minimal). There is no dead, untested (from a user point of view) code.
One of the hardest things when starting on Agile is getting into this mentality of breaking things up into user valued increments. People tend to get mental blocks about it. "It can't be broken up". A brainstorming session with others can often help.
Some things are really hard. For example, what if you wanted to add support for a new platform? In this case, you could start with a very simple subset of the product (where the rest is non-existent or disabled) and build on it.
I generally find that most things can be broken into two week increments. If there is a push for longer, brainstorm a bit on how to break things up. Worst case, you could disable the intermediate forms from the customer. This should be used only if necessary. The exception not the rule.
In some cases, a prototyping spike might be necessary (where you come up with and evaluate some alternatives). The goal in this case is to get more information so that you can leverage that in future iterations.
On what is releasable... This is something that will change as your project evolves in its agile transition. It might start off meaning that the code is done, unit tests exist and QA has tested it. It might grow to mean that automated regression tests have been modified. And that documentation has been done. And that a full regression has been doe. And that marketing materials have been updated. And that production materials (such as a bill of materials) have been updated. Etc. Eventually, as you push the envelope, any iteration really could be shipped (if you wanted to / if it made since for the business to do so).
This can be very powerful. Because you have less and less things that have to be done, you have more flexibility on what you can do. This could be new capabilities. Or it could be deciding that you want to send this iteration's results to a particular customer for some beta testing.