Installing OS X 10.1 "Puma" on new HDD from CD onto a iBook G3
So, as it turns out OS X 10.1 DOES come with Disk Utility, but you need to access it BEFORE you start the installer!  If you start the installer and move past the Introduction section, you cannot get back to the Disk Utility, you have to restart the computer!

So, to format my new hard drive:


Booted up with the OS X 10.1 CD in the CD-ROM drive, held C to boot to the CD
After first load, BEFORE selecting a language in the dialog
Go to Installer > Open Disk Utility... in the menu bar at the top
It found my new HDD in the side menu
Erase and partition it from the separate tabs
Close the Disk Utility and go back to the installer wizard


Your HDD should now show up under the Select a Destination menu in the wizard!

The YouTube video of the installer that klanomath posted was a huge help.  I'm reposting it here for future people:

Mac OS X 10.1 Puma: Installation and first boot

Thanks!