Hard drives usually connect with either USB or Firewire. Both are compatible with PC and Mac.
However, you format the drive with a certain filesystem. Windows uses its own filesystem, and Macs use their own.
FAT32, an older system, can be read by all systems. So it's best to format with this to copy stuff from one machine to another. (So format to this on Windows before copying your stuff onto it.)
Time Machine uses some advanced stuff that FAT32 can't do though (multiple hard links, essentially), so you have to use HFS+ for that, which makes it only work on a Mac. (Though you can get some programs to make it readable on Windows too.)
As for drives: don't shop at PC World or the like if you can help it. ebuyer.com and amazon.co.uk are great, and you'll get a better deal. Seagate, Western Digital (WD), Maxtor, LaCie are all good brands. Just go for what you can afford, with the largest size possible. Right now the good price/capacity point is around the 500GB mark.
Whatever drive, since it's going to be used for backup, try and make sure it has a lot more capacity than the Mac's internal drive. If the Mac comes with 250GB, then a 500GB will be very useful.