It is as with any other methodology. When you create a shippable product, you need to do regression testing. If you are shipping your code with each iteration, you should do regression testing. that said, the agile cycle being short in duration, it may be difficult to accomplish thorough regression testing if done manually.
The best option would be to create an automation test suite for regression which is run as soon as you check in your code into the higher environment. If run every time, you catch your bugs early :). Thats what we mean by Continuous integration - continually integrate your new code with the old by checking in, running automates tests to ensure nothing breaks.