The Flybook is too small to contain a removable media drive, and no external CDROM is provided as part of the package. The first step was to check to see what booting options the Flybook supports.
The BIOS is a recent Phoenix BIOS (bios date 05/10/2004), and contains the following boot device options:

• Removable Devices
• CD-ROM Drive
• Hard Drive
• Network Boot
• RealTek Boot Agent

I originally tried a PCMCIA CDROM drive that came with an old Sony laptop. This didn't work, and wouldn't work under XP either. Setting up network booting sounded like too much aggro so I bought a bog-standard USB external CDROM. Booting from USB mass storage devices is supported in most modern BIOSes. It is probably also possible to boot from a suitably prepared USB flash drive (keydrive), but since the Gentoo LiveCD was (funnily enough) available as a bootable CD, I went the CD route.
The cheap USB CDROM worked perfectly with the Flybook and I was able to boot the CD.

Update: I have tried to create bootable USB keydrives, since this would be a very convenient rescue disk. I have a 1 GB keydrive, which can take a good deal more than a standard CD.
There are two normal methods of making a USB keydrive bootable: either format it as a souped-up floppy disk, or format as a hard drive complete with master boot record (MBR).
I tried both methods on multiple USB flash drives, including USB memory card adapters (using an SD card as the storage) and none of them would boot on the Flybook. This is a shame since it's a really neat solution, and my bootable CD drive is not only bigger than the Flybook, but also requires two cables and a power point.
I have also tried booting off USB floppy drives, and both models (an old Sony USB 1 drive, and a new Sony USB 2 double-speed 'superfloppy') worked perfectly.