Here's what I would do. Use Partition Magic to create two or more new partitions out of the free space on the current partition. One of those should be only a few megs in size, located at the head of the physical hdd, and be the boot partition. This is reserved for your boot loader such as LILO or Grub. The rest of the space should be formatted as Linux ext2/3. You'll need at least a root / partition but then you can add /home, /bin, etc etc.

Now that this is taken care of, run the RedHat installer. Map the directory structure to the current partitions you have reserved for Linux. Remember to tell the boot loader where to go! (I prefer grub to lilo).

And that should be that!

Just realized you IMed me asking how big the partitions should be. The boot loader partition should only be a few megs. 5mb is very, very generous. You might want to do a google search to see how big each partition should be if you want to create separate partitions for separate directories. However, how much you reserve for linux all depends on how big your hard drive is, how much you want to keep for windows, and whether you're going to be installing a lot of linux software or saving a lot of files. Generally, a typical full linux install of one of the latest versions of RedHat can range anywhere from 500 mb to 2 gigs with mostly all software installed. If you can afford to, I would give linux at least 5 to 10 gigs, with room to expand.

Sorry, I forgot to mention you need another swap partition for linux. Set this partition to double the amount of ram you have, if you can.