Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
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.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.