I took a look at the official diagram of your motherboard (or System Board they call it), which is available
here
The interface it uses is IDE. When shopping for a harddrive, make sure you find one that says "IDE" on it, and not "SATA," as SATA is a different connector that will not work.
As far as how big you need, that's a very subjective thing. It depends on what all you want to do with it. If you don't want to mess with partitioning, and were doing ok with 20GB until now, an 80GB hard drive will work (older OS's need partitions above 80GB). If you don't mind doing partitions, or want lots of storage space, go ahead and toss in a 750GB drive. The price has come down massively, and they are a bargain these days (probably the best GB to price ratio of any, at the moment).
For speed, 7200RPM. It's the standard for active drives, and is inexpensive. 5400RPM drives are a bit slow to respond for everyday purposes, and 10000RPM drives are expensive.
When it comes to brand, everybody has a favorite. My personal trusted brand is Western Digital - when I was in PC tech classes, my hardware instructor swore by them, and they've never done me wrong. I've known others who were long-time devotees of Seagate and Maxtor brands as well.
A couple examples:
80GB quick fix
750GB monster
There are many options in between, of course, depending on your budget and your goals for the system.