Mavericks told me I needed to replace my battery, and my battery life was down to 3-4 hours after 250 cycles or so.
Could not have been easier. Used my coworker's iFixit toolkit. Took me about 20 minutes and I was being super careful. Literally unscrew the case, unscrew the battery, release the connector, and replace.
This is a good moment to do a little cleaning - I had some dust in there. Canned air worked but I bet a mini-vac with a soft brush would have been better. Wiped down the bottom case cover with some alcohol.
There are a few sizes of pentalobe so make sure you have the biggest one that fits before you apply torque!
Rule of thumb: the short screws are where the case is thinnest. Duh!