Is there any difference between HD's? Is there a specific kind of HD that you have to buy for a Power G4 Mac, or can you just buy any old harddrive (ex. one from a pc computers store)?
You should be able to use any old IDE/ATA drive.
If you wan't to know which types to look for find your machine here.
I've personally never tried any old random drive in a Mac, and in theory there are some with firmware limitations that won't work (that might be out of date news nowdays), but I know a couple of people who have bought obscure HDs that have worked fine.
Also, if your machine happens to be ATA/66 for example and you find a cheap ATA/133 then that should also work fine, it'll just scale down to the slower speed.
If you go for something by Maxtor, Seagate and the other big names there should be no problem.