How do I go about buying a Harddrive?

Well first off take a look at these two links . It looks like G4s are not very easy to replace the hard drive yourself, and I;m guessing if you are asking this question you would not be comfortable going through the trouble of that yourself.

Check out this post and maybe you can find more info starting there.

As far as just hard drive selection. You need to be looking for 2.5inch drive, at least 5400 RPM and ATA, not SATA. I believe for the G4s.

The “keys out of order” error indicates serious corruption of the filesystem on your hard disk. This is a software, not a hardware problem

First run fsck in single user mode a few times to see if it fixes it self since it says it is “Rebuilding”. If not, There are programs such as Diskwarrior that have been known to fix that exact issue but cost money. If I was you. Since you are ready to buy a new hard drive already, Backup the one you have now or at least get all your important data off and onto an external hard drive then reformat(erase) your hard drive and reinstall whatever operating system you are running and the hard drive should be fine

I have tried many times, eraseing my harddrive and reinstalling OS X. and my computer works, for a few minutes. Then as I am installing software updates and such, my computer freezes, and no matter how long I wait I eventually have to force restart my computer. When I restart I get a “grey or blue” never the start-up apple. I have tried starting up in single user mode, but i still get a grey or blue screen…

Thank you both for the help!

If the computer freezes during an update it could still be a problem with your network connection not downloading the updates correctly, But if your sure its a dead hard drive then I get mine from CDW. i bought this for my G4 Powerbook TI

http://www.cdw.com/shop/products/default.aspx?EDC=1124121

I got a hard drive replaced in a lap top for about $130.00 (hard ware and labor) at a computer shop just this year. Goodluck!