Apple will not replace your battery if the computer is over one year old. Even if you have AppleCare.
Also Apple officially considers 1000 charge cycles the maximum life of your battery. The 80% after 1000 cycles is what they state, but is more of a guideline. Many batteries consume before 1000 cycles.
For example, someone leaves their computer plugged in for the majority of time for just under three years. Lets say they have 100 cycles on their computer. Obviously the battery is going to be junk at this point. It's way under 1000 cycles. That is why the 1000 cycles/80% is a guideline. Mainly marketing anyway.
If your computer is under the one year mark, Apple will replace the battery ONLY if it fails their diagnostics. This is a comprehensive tests that looks at more than just cycle count.
This article shows what Apple considers the maximum battery life of their notebooks. So once again, they will not replace your battery for free. I believe the cost is $129 in the US.
http://support.apple.com/kb/HT1519
Also the article listed in the post from gr8tfly above says UP TO 80% capacity after 1000 Cycles. Also says UP TO 5 years. That is the maximum one can expect while using the battery. This is marketing, rarely anyone gets that. Many people take this as the actual set in stone warranty information for Apple batteries, but sadly it is not. They only cover the battery for a year, and it actually has to completely fail within that year in order to be replaced.