You can buy a hard drive from a PC store, it'll work with the Mac, being a G4 it can vary from Ultra ATA/33 (ATA-4) to ATA/100 (ATA-6), most of the Power Mac G4 models have a limited hard drive support, up to 128 GB per drive, MDD G4 support bigger HDs.
You can place the blank HDD inside the PM G4 and boot from the Mac OS X cd/dvd disc, you just need to initialize your new hard drive so your Mac can recognize it. See it like installing some drivers in the windows-dos world.
Once Mac OS installer starts go to the Menu 'Utilities' (or something similar, I can not recall 100% since my Mac OS X runs in another -non english- language) and choose 'Disk Utility', once you open Disk Utility:
- select the drive
- go to the Erase tab.
- choose type of partition (Mac OS Extended Journaled)
- type a volume label.
- I would check the box that says "Install Mac OS 9 drivers". If this option is not selected, this device cannot be used by a computer running Mac OS 9. This option does not affect Classic.
- Click Erase
- read the advice and Click Erase again if you are sure the correct drive is selected, if there is only one, there is no place to mistake.
Initializing the disk takes only a few seconds. As soon as the process is done, your new disk will mount, ready for you to fill. And you will fill it, maybe sooner than you think.