I just replaced the HD and when I start it up holding down the "c" key

Welcome to the Apple Support Communities

You have the wrong disc. Call Apple to get replacement discs > http://support.apple.com/kb/HE57

You need to boot from an OS installer CD or DVD, then format the new hard drive, and install an OS.

What version of OS are you using? Is this OS X ro something earlier. Exactly what PB model are you using?

It doesn't matter if you want to install OS X. On your tags, I see that you mention OS X 10.6. 10.6 is an Intel-only OS X, so you can't use it on a PowerBook with the PowerPC processor. You need Leopard or Tiger

Press the trackpad while your computer is starting to eject the CD

It should work properly, but if Apple Hardware Test says that your machine isn't compatible, probably it's the wrong disc

OK. From a previous post:

"Powerbook G4 15 inch and 17 inch software install and restore Mac OS X version 10.3 AHT Version 2.0.6 DVD version 1.0-

That is not the installer disc. That is the AHT, Apple Hardware Test, disc. You need a disc that says Disc One of OS X Install Disc for Panther, 10.3. Or you need a later OS X full retail installer disc for a version of OS X between Panther and Leopard - 10.3 to 10.5.

Do you have such? If not, then you will need to get replacements for the original discs that came with the computer by Contacting Apple for support and service - this includes international calling numbers.

You can give it a try:

Drive Preparation

1. Boot from your OS X Installer Disc. After the installer loads select your language and click on the Continue button. When the menu bar appears select Disk Utility from the File menu.

2. After DU loads select your hard drive (this is the entry with the mfgr.'s ID and size) from the left side list. Note the SMART status of the drive in DU's status area. If it does not say "Verified" then the drive is failing or has failed and will need replacing. SMART info will not be reported on external drives. Otherwise, click on the Partition tab in the DU main window.

3. Under the Volume Scheme heading set the number of partitions from the drop down menu to one. Click on the Options button, set the partition scheme to GUID then click on the OK button. Set the format type to Mac OS Extended (Journaled.) Click on the Partition button and wait until the process has completed.

4. Select the volume you just created (this is the sub-entry under the drive entry) from the left side list. Click on the Erase tab in the DU main window.

5. Set the format type to Mac OS Extended (Journaled.) Click on the Security button, check the button for Zero Data and click on OK to return to the Erase window.

6. Click on the Erase button. The format process can take up to several hours depending upon the drive size.

If the installer disc does not provide the security options for Steps 4-6, then just skip them. After formatting is completed quit DU and return to the installer. Now install OS X onto the new drive.