1. What's a reliable brand?
All the techie people I've talked to have a different "OMG THIS BRAND ALWAYS FAILS" horror story, and it's always with a different brand. Hard disks are delicate devices* so no matter what you buy, you should be making regular backups.
2. What do IDE, SATA and PATA mean?
Like was mentioned, IDE is the older ribbon cable design, and SATA is the new, tiny cable design. SATA and SATA II drives have a faster data transfer speed than IDE drives do. PATA means the same thing as IDE. If your motherboard has support for SATA or SATA II, get a SATA II drive, as it will be easier to install** and be slightly faster.
3. Does the rpm really make that much of a difference? If so, what would be the recommended minimum?
Yes, but it's not really worth it to buy a 10,000 RPM drive just yet, because they have a very bad cost/size ratio. 7200 RPM drives are generally fine.
4. What does the size of the cache affect?
Speed. A cache is a little RAM on your hard disk that holds data that's nearby the data it's been requested to read, so that if it turns out that a nearby file is requested, it can be accessed much faster. I've never seen definitive statistics about how much of an improvement you can get with a larger cache, but I wouldn't fret too much about the cache size unless the drive you're looking at has substantially less than whatever seems to be the average these days.
Super bonus hard disk speed explanationHard disks work by spinning a magnetic platter around very fast and sweeping a mechanical arm over it that reads the data. In order to access any byte on the disk, three things have to happen:
1. The head (at the end of the mechanical arm) has to move to the correct "cylinder" of the disk. That is, it has to move to the correct radial distance from the center of the disk. This is generally referred to as "seek time".
2. The head has to wait for the drive to rotate until the requested bytes are underneath the head. This is where higher RPM drives help; it takes less time for the part of the platter where the data is stored to reach the head.
3. The data has to be transferred down the hard disk cable to RAM. This is where the difference between IDE and SATA comes in.
So as you can see, there are all kinds of considerations, but don't worry about them too much. Just buy SATA if your motherboard supports it and don't go too low on the RPMs (e.g. there's no excuse for putting a 5400 RPM drive in a desktop computer these days) and you'll be fine.
* I mean it's a tiny magnetic head floating a hair's width above a rapidly rotating piece of metal. There's a reason one kind of drive failure is called a "head crash". If you looked at such a catastrophe under a magnifying glass it would probably look like a tiny Hiroshima.
** If you are putting an IDE drive on the same cable as another IDE drive you have to be at least slightly conscious of the fact that when putting two IDE drives on the same channel (that is, the same cable), one of the drives has to be set as "master" and the other one "slave". Most drives have a "cable select" option now that handles this automatically so that shouldn't be a big deal but if whoever put together your computer was an idiot you might have to change jumpers around to make it work.