There are already tons of articles, howtos on this topic but one more does not hurt. My situation was kind of different as well.
One of my colleague left the company and I inherited his Lenovo T60 x86_64 laptop. The machine had Fedora 8 installed in it and I needed to setup dual boot with Windows XP and Fedora 9. Of course the easiest would have been to upgrade to FC9, partition the disk with gparted and install Windows XP on new partition. But nothing in life is this easy so why this should be. I had a previous experience of installing dual boot on Dell desktop way back in 2000 with Windows ME and Red Hat version 6 IIRC. But back then I had bought additional hard drive, one for each OS. Anyway, following is what I ended up doing in this case.
For some reason gparted could not partition my hard drive (dev/hds). It kept failing and error was not very descriptive. Most of these articles suggested that it's much easier to install Fedora on machine with Windows than other way around. With Microsoft, you should expect this anyway. When I tried to boot from CD with Windows XP, it did not boot. I think XP was confused with linux partition and it did not know how to proceed. This meant that I had to reformat the whole hard drive. Since I did not care about data that were already there, I could freely reformat it. The easiest way to reformat in Fedora is to sudo as root and do :
dd if=/dev/zero of=/dev/hds bs=521 count=1
This command deletes partition table and XP installation CD wont see any Linux distro in harddisk. If you restart, your BIOS should not see any OS.
I restarted with XP installation CD on it, XP formated the whole disk with NTFS and installed itself. Now comes the fun part of installing Fedora 9. I prefer Fedora Live CD than full CD ISO or DVD ISO. I rebooted with FC9 live cd, connected to wireless network in case I needed to download something explicitly and selected the option "Install to hard drive". After hitting next button couple of times, it gives you an option to how to install to hard drive. I chose 3rd option which allows to partition hard drive. I shrinked existing partition to 50G so that meant 50G will go to XP and the rest to FC9. Follow next couple of times, Fedora does its things and installs itself.
When I restarted, the first screen says Fedora, hit enter and then GRUB bootloader screens shows up. It gave me two options. One said Fedora and other said "Other" which is Windows. I think you can rename "Other" to Windows so that it's clear but I did not care. Selecting "Other" takes you to the familiar XP startup process.
Overall my experience was not very painful.