Steve. As Mark said, some use IDE (also known as ATA or PATA) drives and some use SATA drives. The connections are different, so you need to find out which the unit you are looking at has. Also check whether you need 2.5 inch or 3.5 inch (more likely the latter).
IDE drives are obsolete and supply of new ones has all but dried up, so you'll most likely have to buy a second hand one.
Yes, they're the same as desktop PC hard drives.
As regards capacity, you'll get about 1 hour of recording per GB, so a 500GB drive would hold very roughly about 200 full-length standard definition movies.
When you fit a new drive in the PVR it'll usually offer to format it, so don't worry about formatting. The format is not compatible with Windows - if you take a drive from the PVR and put it in a desktop PC, it wont be able to read the files.
Are you looking at the Topfield 5810 PVR by any chance? I got one of those minus the hard drive from ebay a couple years ago and fitted a drive. It's a nice machine, a bit quirky but I don't think any of them is perfect.