It's acutally unbelievably easy. The biggest issue is to ensure you have a seperate partition on your hard drive or a whole seperate hard drive altogether. This is where you want to install linux.
One that is set up, simply boot off the CD and you should just follow the steps to set things up. The hardst part you will run into is setting up the partions within linux. You will need at the very least 2, 1 for the data and 1 for a swap area. make sure you have the swap as roughly 1.5 times the amount of ram you have. Before I get flamed, let me say there are tons fo theories on how you should partition the data part of your install (such as setting up /home as a seperate mountpoint), but it's an advanced topic for someone just starting out with linux.
the next issue you'll run into is where to install the boot loader. probably, your best option it to find an available floppy and install the bootloader there. as long as this floppy is in the floppy drive when you start your computer, it should start up linux. no floppy, no linux. other options include MBR (master boot record). this is also easy, but it makes it much harder to get rid of linux if you want. if you every get rid of linux, you will have no way of getting to windows (you would have to reinstall the windows bootloader or use a 3rd party one). there's a couple other options, but that's what i recommend
beyond that, itshould be very simply to get things installed.
as far as a distro, i highly recommend ubuntu. it's debian-based, and apt rocks for installing new packages (especially hen combined with synaptic package manager).
www.ubuntulinux.org
i use it on my laptop and it works like a dream. the next verion (hoary hedgehog) is going to be final come april. you could install it now and just do a `sudo apt-get upgrade` to get any of the latest packages. alternatively, you could install warty warthog and after changing your repositories from warty to hoary, just do a `sudo apt-get dist-upgrade`
p.s. it makes life a lot easier if you have another computer attached to the internet to use as a reference in case you're unsure about anything