G'day and welcome to the forums.
Well first up what operating system is it currently running? They came with Classic OS 8, and require OS 9 in order to upgrade the firmware prior to installing any version of OS X. Trust you are pretty conversant with working inside a computer as G3 can be difficult to crack and change hard drive's in.
When you get the drive in, OS 9 installed, firmware updated as below link, then look for the Panther OS X.3 CD set which may be difficult as Panther was the first OS to be released on DVDs from memory. Make sure you purchase a black retail install set and not some silver grey discs which were supplied with another machine.
http://support.apple.com/kb/ht1395
Do not attempt to install OS X without downloading and installing the firmware update Document No.60384, third from the bottom on the first section of the link.
Also for your model 512MB is the maximum memory so do not expect too much from the machine.