the safest way to remove your XP partition(s) is with the same CDROM used for the XP installation.
I don't know about XP but the Windows 2000 CDROM when booted allows you to installs Windows2000 or to erase any Windows partition.
Use it to remove all Windows partitions, reboot ( so the changes will be saved ) and insert your Linux CDROM.
Most Linux distros are "newbiew tolerant"
they will automatically create at least 2 linux partitions / and /swap
As a linux newbie, I would stay away from Debian ,Slackware, Gentoo and Linux from scratch
They are all great distros, but I would never recommend them to a newbie.
I would suggest Mandrake, Fedora ( I use it ) , Conectiva ( If you are from South America ), Suse.
But maybe the best option before scrapping your windows partition should be to download and burn a CDROM with Knoppix that you could run directly from the CDROM.