We are starting with a fresh machine with no regard for current data on it. If you wish to preserve an installation, I recommend picking up a copy of Partition Magic or a similar utility to reduce the size of your Windows installation to make a partition for Linux.

How much should you leave for Linux? I think 4GB or so will keep you pretty happy, but honestly, hard drives are so big, you shouldn't feel bad about giving it more.

Instructions for installing Windows.

1. Format using the FAT file system. Why? Linux speaks FAT really well. While NTFS is nice, the Linux driver is sort of beta right now. Since it will be handy for you to access the Windows side of things from Linux (say you store your MP3s on your Windows partition) I'd say stick with good old FAT.
   
2. When you reach the part where you are setting up your Windows partition, simply create an initial partition for Windows that is 5GB less than the size of the drive. Then continue to install Windows as you normally would.
   
3. After you've installed Windows, pop in your Linux distribution CD (as usual, I recommend Red Hat for its nice install). When you reach the point where it asks about partitioning, choose the partition utility that you prefer. I usually use fdisk, but many will prefer the easier-to-use Disk Druid. For the purposes of this discussion we won't go too deeply into partitioning schemes and will install the Linux distribution into one partition with type 82, the default (something unwise to do for a server and many clients, but we want to show off dual booting, not partitioning strategies) and the swap (type 82) in another. What size should the swap be? Depends on how much memory you have. Twice the physical memory is one rule of thumb, but you really don't need more than 256MB on a desktop machine.
   
4. The last bit of magic is to make the Linux root partition active and making sure the Windows partition is not active. If you forget this step you will either jump directly into Windows, or you will get an OS not found error as your computer's BIOS will be unable to decide which partition is the active one.

That's pretty much all there is to it. During configuration, Red Hat will recognize your Windows partition and (mostly) automatically add it to the boot loader so you will see, in the loader, an option to load Windows.

Once in Linux, you can mount the Windows partition by using a command like "mount /dev/hda1 /mnt/dosc" and then you can have full access to the Windows side of things from Linux.