I realise the Apple website has some good guidance for that, but I thought I'd write down the bit where I went wrong in case it helps some other folks.
To trigger the keyboard to re-pair (once the original device is unavailable), press and hold the "on" button until the green light at the top right glows solidly for a bit. Then you can tap "keyboard" in the Bluetooth screen of the new device. It should then come up with a pairing code to type on the keyboard. Don't forget to press Enter...
Note: When you're trying to pair a keyboard that's already been connected to another device, you seem to need to make the first device unavailable.
For example - I have a keyboard which was already paired to my iPhone. To pair the keyboard with my iPad, I had to turn off Bluetooth on the phone before the keyboard would look around and talk to the iPad.