Use coconutBattery to see the status of your battery. These steps are both for the old Macbooks and the new (unibody) Macbooks. Not sure about Air but it should work as long as you can open it.
Now do all these steps (I had to do all to make this warning go away).
1. Charge battery to 100% (charger green light).
1a. (probably not necessary) Discharge battery using Caffeine app, until the Macbook turns off, wait a few hours, then charge it back to 100%.
2. Shut down completely. Remove charger.
3. Open the bottom of the MacBook using a screwdriver. (You can leave it open until step 16)
4. Disconnect the battery.
5. Use a cotton swab with 70%+ alcohol and clean the contacts of the battery connector.
6. Hold the power button for 30 seconds, then press it a few times more.
7. Connect the charger (not battery) and wait a few seconds.
8. Reset SMC – press the (left side) Shift-Control-Option keys and the power button at the same time, hold for about 1 second, then release them all at the same time.
9. Reset NVRAM. (Steps 9a and 9b)
9a. Turn the Macbook on, then immediately press and hold the Command-Option-P-R keys before the gray screen appears.
9b. Hold the keys down until the computer restarts and you hear the startup sound for the second time. Then release the keys.
10. Let OSX boot or turn the Macbook on if it’s not on.
11. Now connect the battery while the Macbook is still on – this step was probably most important for me.
12. The battery indicator in OSX should show that the battery is now connected and at 99% (or 100%), and there should be no service battery anymore.
13. Wait a few minutes.
14. Shut down the Macbook completely.
15. Disconnect the charger.
16. Close back the Macbook case and screw it back on.
17. Turn on the Macbook and log in. The service battery warning should be gone.
18. Use Caffeine to drain the battery, do not turn off the Macbook until it shuts down itself.
19. Charge to 100%.