Service Battery Warning

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

Solution 1:

ifixit.com sells a battery replacement (and almost any other part for your laptop), you might want to check it out. Here's the link http://www.ifixit.com/MacBook-Parts/MacBook-Pro-13-Inch-Unibody-Mid-2009-Battery/IF163-003

The part is out of stock, so you might want to be notified when it is available, it's all in the link.