Even if I don't know how to implement something I can almost always write a test for it and If I can't figure out how to write a test for it I have no business programming it in the first place. - Kent Beck
Many processes in agile are mutually supporting. A good example of this is testing and its relationship to the development iteration.
Frequent Releases
If you want to do a release at the end of a 1 or 2 week iteration, then you will need to have confidence the changes you have made do not break the application. To achieve this, you either do a lot of manual regression testing or you have extensive automated regression test coverage.
Each time you add new functionality to an application the amount of regression testing increases. So, if you are taking the manual regression testing approach you are in trouble. The more work you do, the harder testing will get. It is obvious how incompatible this is with short development iterations.
One of the keys to a successful Agile approach is to ensure you automated your regression test coverage. This is a significant overhead and will have an impact on your planning and scheduling. But the benefits are huge: greater confidence leading to more frequent production releases.
Acceptance Criteria
My preferred approach is to include an automated functional test for each acceptance critera for every story taken in a sprint. That way, at the end of each sprint the pool of automated regression tests has been expanded to include the newly added functionality. The overhead cost of this is roughly 20-30% (depending on the nature of the test approach you use and the experience of your team at writing functional tests). Clearly, to justify a cost of 20-30% the benefits must be significant.
Long term view
The real challenge is taking the medium to long-term view, rather than focusing on immediate productivity. This is a managerial challenge and not a technical one.
The best way to justify the cost is to think of the evolution of the application. If you want the application to be used for several years, then the automated regression tests may end up being run literally thousands of times. Now imagine the labour cost of having those tests run manually.
As is so often the case in development, you pay a price in the short-term for what you gain in the long-term. If you want a product that will last, get good functional test coverage!
Testing is critical in agile. Focus on it, do it right and you will go a long way to achieving an agile approach.