If you're booting off the CD then you might have to do some work after you boot. Red Hat has a rescue mode that you select after booting. Under SuSE we have to boot into the installation and then use the ctrl+alt+fn key to locate a shell prompt. You can use this shell prompt to continue with the recovery.

Boot in and enter the following at the prompt.

mkdir mount

First, create a mount point. The root partition of your lost Linux installation will be mounted here.

mount /dev/hda6 mount

Mount the root filesystem under "mount". If /boot is a separate partition then mount that under "mount/boot".

mount /dev/hda1 mount/boot

The "/boot" partition has been mounted under "mount/boot"

chroot mount

Run a shell with your root directory as "mount". What this does is that "mount" will become your root directory as referenced by "/". So, now when you say "cd /boot", you'll actually be changing into "mount/boot".

/sbin/lilo

Re-run LILO. This will install LILO back to the MBR. At next boot the LILO prompt will be back.