Physically install the drive, restart the computer with your OS DVD in the drive, hold C while booting, and proceed to run Disk Utility.
You'll then format the drive as HFS+ Journaled with a GUID Partition Table (assuming your on an Intel Mac, if G4 you'll have to use Apple Partition Map). When that's complete, you just run the OS installer off the same DVD that's already inserted.