before you do format, you have to fdisk the hard drive. first get a win98 boot disk. and since this is probably the first time you do this, i will suggest you unplug your old hard drive (so you won't deelte anything in the old drive). Plug in the new hard drive, and use the boot disk to boot up the machine.
after it is booted, type "fdisk", and you should have 4 option. choose option 1 to create partition. the easiest way is to create one partition (you can play around with it to see how you can create several partition, since you have nothing in the hdd anyway).
after that, exit fdisk and it should ask you to reboot. reboot again, and the type "format c: /q/u" if you are going to use it as a slave drive. if you are going to use it as master and will be the boot up hard drive, type "format c: /q/u/s"
after that, you should be good to go.