Time Machine External Drive
Make sure the drive is from a reputable supplier.  I've used Western Digital external drives without a problem.

When you get the drive it will most likely be formatted in NTFS format (for Windows), so when you plug it in, you will need to open Disk Utility and repartition it as HFS+

A Firewire 800 drive is fastest, although since the backups are incremental and happen in the background (with only the changed bits/files going across), I believe the cost/benefit factor is weighted towards getting a cheaper but higher capacity USB 2.0 drive.  That's just my opinion.