It is a very easy task and I had no problems with a bluethooth keyboard (Thinkpad).
A) You can use the "add new device" wizard of Ubuntus standard bluetoth wizard (indicator symbol or system settings). It gives you a number. This number you simply enter on your keyboard, an press enter. Then the dialogue vanished and devices are paired.
B) Use Blueman (
sudo apt-get install blueman) and the "pair" command to easily add new devices.
- search for new devices with blueman
- right an press "pair"
- enter "0000" on your UBUNTU PC (you can use any custom number
- hit ENTER or press "OK" on the pc-dialogu
- immediately AFTER THAT, type "0000" on your BLUETOOTH
- hit ENTER on the keyboard
That's it. Devices paired.
Tested on Ubuntu 12.04 LTS and 14.04 LTS with Blueman and a Thinkpad Bluethooth keyboard (which should be same as a mac keyboard, due to bluetooth standard for input devices) on a Thinkpad W510, a Thinkpad X201 and a hinkpad X61s.