Bottom line is :
- make sure your hard disk has enough free space.
- if possible, resize partitions to make some raw free space. (if not possible, don't worry, many installers will do it for you)
- get a distribution as .iso file.
- turn the iso into a bootable cd/dvd.
- get started.
Here is a video how-to covering the above steps for Ubuntu (see "installing a Linux Ubuntu LiveCD") : http://www.ubuntuvideo.com/
Linux From Scratch. Version 4.0 - Linux From Scratch (LFS) is a project that provides you with the steps necessary to build your own custom Linux system.