Just installing Ubuntu is no issue at all. You don't even need to create a seperate boot partition, because it'll boot just fine using the Mac's legacy booter. However if you're a Mac Mini owner and want to boot headless, there is only one solution (and a workaround that uses a 'dummy monitor dongle', which is not what I would want). This solution is making use of the EFI features of GRUB 2, which I'll detail in the rest of this post.
When the installation is done, install hfsplus and hfsprogs so you're able to create HFS+ volumes (you probably only need one of those, but it wasn't exactly clear for me which one to use and due to lack of time I haven't looked any further yet). Copy files from your boot partition to a temporary space, then unmount and format the boot partition as HFS+ (mine is /dev/sda2):
# mkfs.hfsplus -v boot /dev/sda2
Edit /etc/fstab to use the new boot partition as boot partition:
...
/dev/sda2 /boot hfsplus defaults 0 2
...
Unfortunately it seems UUID's can't be used for HFS+ volumes at the moment, so hardcode the device name in there.
After creating the volume mount it again and copy over all the files from your temporary space.
Now install grub-efi, this will automatically remove grub-pc. Generate a GRUB EFI executable using the following command:
# grub-mkimage -o /boot/grub/grub.efi -p /grub part_gpt hfsplus fat ext2 normal sh boot configfile linux
You actually don't even need the fat and ext2 modules and probably more can be stripped, but I haven't experimented with GRUB 2 a lot yet, that'll be for another day (and another post).
We're almost done, now it's on to getting the Mac to actually use our EFI enabled GRUB. First toggle the boot flag on your shiny HFS+ partition. Run parted (or any other GPT-aware partitioning tool) and type:
(parted) set 2 boot off
Parted will probably tell you the disk is in use and you need to reboot for the change to become effective, but it doesn't matter for us.
Now the final step is to tell the Mac (or actually, the filesystem) that our grub.efi is bootable so it'll show up in the Mac boot menu. There should be a utility call hfspbless, which allows you to do this from within Linux, however the first hit on Google doesn't seem to offer a quick guide, so I skipped this part. Instead, put in the Mac OS X install DVD. As soon as a menu bar shows up (I believe you have to click next at least once), fire up a terminal. In the terminal, enter the following:
# mkdir /Volumes/boot
# mount_hfs /dev/disk0s2 /Volumes/boot
# bless --folder=/Volumes/boot --file=/Volumes/boot/grub/grub.efi --label boot --setBoot
The bless command has now set some metadata on the HFS+ filesystem that the Mac uses to identify a native bootable image. I assumed label should set the label accordingly for the boot menu, however my entry showed up as 'EFI something' IIRC, but I can't care more or less since it's a server and I'll never see the menu anyway. Now reboot and enjoy!
This did the job for me, however there are a few issues I still have to take care of. The Mac created a fake MBR partition map for me, which I don't need and don't use. It now shows 'Windows' as option in the Mac boot menu, but luckily it starts Linux by default. Also, the MBR partition map is out of sync if you do stuff with the GPT partition table. I used rEFIt to resync the MBR table, but when I figure out how to remove the MBR that's what I'm going to do.
Also, there's a file called Volume Name Icon on my boot partition. I guess this is used for the Mac boot menu, so it probably can be changed easily too. However I have no clue what the format is, I'll have to look this up some day and change it for a genuine Tux!