simsaladimbamba is right, boot to the install DVD then go to Disc Utility. If you don't see the drive there as available to be formatted you have a larger issue.
OSX won't offer to install until it sees a properly formatted drive available, and that's not going to happen until you get into disc utility and do it.