I've set up a triple boot with Ubuntu, XP and Vista, i start with a clean drive, no partitions. If you're installing onto a drive that already has partition/partitions on it you need to delete those. To do this stick in the windows CD, boot off of it, this will take some time, then just follow the on screen instructions when it comes to deleting or creating partitions. Then I create a partition for XP using the NTFS format, of what ever size I have set aside for XP and leave the rest of the drive unpartitioned. Then i move on to Vista, again create a new partition for it in the unpartitioned space for the size of disk I've set aside for Vista, and finally i load up Ubuntu and install it on the largest unpartitioned space. Not forgetting of course to set aside 512 Mb as a 'swap space' partition on the drive, this as i understand it is just a space set aside as virtual ram on you're hard drive that an OS like Ubuntu will recognize, i'm not sure if XP also uses it, i just know i should have it factored in when i'm working out how much space each OS will need. XP or Ubuntu will ask to create a swap space partition, just say yes and give it some space, i generally use 512 Mb, for no particularly good reason though. And thats it, easy as pie
The reason i do it in this order is because of boot loading programs, XP's one sux. No matter what i have on the machine, after installing XP that's all i boot into, with no options. Vista is slightly better, if i have any older version of windows installed it gives me the option of which windows i can boot into. But Ubuntu comes with the "grub" boot loader, which recognizes all operating systems and gives me the option to boot into the one of my choice.
I've never personally used Fedora, but since it's also a flavor of Linux, it'll probably have grub to, so weather you install Ubuntu or Fedora last probably wont matter.
So to summarize, delete all partitions on you're drive (make very sure you have all important data backed up on another drive, when you delete those partitions all you're data go's bye bye) then create each partition on the unpartitioned drive space as you install each operating system. How much space you set aside to each OS is up to you.
Things to take note of: only have the drive you're installing the OS's on plugged in when installing new operating systems, it just makes it a bit more foolproof. You don't want to loose any backup drives accidentally. And factor in about 512Mb swap space for the Linux installs.
And if you don't get grub on the final OS install you can install it later off the Ubuntu CD, Google it for details if you get stuck, but if you install Ubuntu last it wont come to that.