Traditionally, software development has been done in a "waterfall" process. First you collect the requirements. Then you design the software. Then you implement it. Then you test it. Release cycles have typically been on the order of every 6-18 months.
Approaching Things Incrementally
Agile development approaches things in an incremental fashion. You break things into time-boxed chunks called iterations or sprints (frequently 2 weeks). Within the iteration, you do the full life cycle, but on a much smaller scale (only focusing on the most important functionality). You typically come into the iteration with a high level understanding of the increment that you are trying to take on (often called a story). At the beginning of the iteration, you define the more detailed requirements (acceptance criteria). You develop and test the story within the iteration.
The goal is to keep things such that every iteration could be potentially released. Each iteration is demonstrated to the customer (or a proxy such as a product manager). This results in changes to the backlog of stories for future iterations. You can release at whatever frequency makes sense for your customers. Hosted services might actually release every two weeks. Smaller releases are encouraged as they provide more opportunities for feedback from the larger customer base.
Being Predictable and Transparant
Agile has many advantages over waterfall. In waterfall, you have the illusion of control. You typically have a project plan which covers the duration and show all of the key tasks that must be done. In reality, the project is typically much too complex to accurately schedule. For example, once you finish development, it is very hard to predict how long it will take you to find and fix all the defects.
In agile, you tackle things in much more manageable chunks. It is easier to predict how long items will take that are days long (rather than months). As for defects, these are kept in check as you go. It is much easier to diagnose / fix a defect if you know it was introduced within the past two weeks (rather than 6 months). With agile, you know you can make your dates. The question is what will the functionality be? In waterfall, both dates and functionality are in question.
Focusing on What Will Make a Difference
Perhaps even more important than the predictability gained is the productivity gains. Agile is all about prioritizing and tackling the most important stories. And then re-prioritizing every iteration based on what you've learned / changes to your marketplace. As a result, you might only get the first couple of stories done related to a particular set of functionality before you realize that it is enough (i.e., it is more important to do other things than to continue on that line of functionality).
In waterfall, you set the functionality up front. So at the end of the 12 or 18 months, you have the system that would have been a good fit for the market 12 or 18 months ago, not the market of today. Without the feedback loops, you tend to go deeper into things than you need to (resulting in unused features). Finally, because you're releases are so infrequent, users tend to pile on with their requirements since they know that if it doesn't make it, they have to wait a long time for their next opportunity. Agile's productivity gains are as much about what you don't do as they are about what you do.
Tackling the Challenges
Agile isn't without its challenges. It takes time to adjust to the new approach (and to get the infrastructure in place and working well to support it). Another challenge is that you have to re-educate your customers (internal and external) to think in terms of priorities rather than fixed feature sets. But agile is worth the cost. Once you do it and see how well it can work, you'll never go back.