I have a 13" Macbook Pro (2009) and I randomly get the "Service Battery" warning. I haven't noticed a huge decrease in battery life but the cycle count is at 725. I'm out of warranty, and so I'd like to do it myself, but I couldn't seem to find a replacement battery on Apple's web site. All I could find was this article, but I'm out of warranty. Where can I get a new battery? Also, if I don't notice a huge decrease in battery life, should I even be that concerned over this? I've included a few of my stats from system profiler.
Charge remaining (mAh): 4102
Full charge capacity (mAh): 4102
Condition: Check Battery
Amperage (mA): -477
Voltage (mV): 12271