You don't have to install it over XP, they can co-exist. My personal experience is that you want to run Redhat first, as it's been a fairly easy-to-config distro on the dozen or so systems I've rolled it onto.
Either use Partition magic, clear out some space and put linux on that way, or rebuild/repartition your drive. If you end up not caring for Linux, you can reformat that partition from Windows.
You can either install the boot loader (Grub or Lilo) on your MBR, or - if you want to just "check it out", install it to a floppy. If your hard drive's MBR stays Windows-managed, you can simply pop in the disc if you want to boot to your Linux partition (and have less of a headache afterwards if you decide not to use it).
Hope that helps.