The system recovery CD should be bootable upon itself. Your computer must be set to 'boot to CD' as first boot option.
If the 'new' harddrive is indeed new, then it must first be prepared to accept the operating system. It should have come with a utility floppy or CD disc that will do this for you. If it did not then go to the harddrive manufacturer's website and locate the maintenance utility and download it and either to a floppy or cd. There should be online instructions for how to do this. Once you get the utility disc...boot to it and it will find the drive and just follow the simple instructions to prepare the new drive.
Once that is done then remove the utility disc and install the recovery disc and boot to the disc...on boot you must watch closely for the 'boot to CD hit any key' notice to tell your computer that it is ok to boot to the CD. Then it is simple follow the instructions to install the operating sytem.
You will also need to have the motherboard driver disc handy also. I believe that the hadrdrives for that system are SATA if so then you may have to install 3rd party drivers to get the harddrive to be seen by the installation disc. Try to install the operating system without using the sata drivers as it maybe incorporated on your mobo . If the installation disc can't find your new harddrive then you will need to install the 3rd party drivers.The SATA drivers are located on the mobo driver CD and installation instruction will be included with them.