The accepted answer does not work with the latest OSX (El Capitan). Here are the updated instructions.
Firstly lets all acknowledge, this is not Apple's finest moment in user experience engineering. Onwards.
The Apple bluetooth keyboard is infuriating because the little green light doesn't give you enough information to indicate if it is turning off because battery is dead or for other reasons. So you're a bit blind if the batteries are dead, but otherwise the following instructions should work.
- Go to System Preferences, then Keyboard
- Set Up Bluetooth Keyboard...
- Hold down the power button of the keyboard (the one on the tube, on the right side, not the power button key on the top right of the
- If you hold it down for 4 or 5 seconds, the setup panel will change from "No keyboard found" to "keyboard found". Don't let go of the button!
- Now here is the key step. While still holding down that power button, don't let it go, you need to use your mouse to press "Next" on the dialog.