I just got done installing xubuntu on a B&W Powermac g3, and it wasn't that easy.
If holding down C doesn't work (like it didn't for me) you will have to go into Open Firmware and boot from the CD from there.
When the computer is first booting up, hold down Apple+Option+O+F
then type
boot cd:,\\yaboot
then type "install" at the prompt.
Be careful not to delete your Mac OS partition. I didn't have to worry about this because mine is just a linux box.