Just to add for posterity, the G-Tech series are certainly a bit more money than the third party solutions offered here, but it literally is plug and play - absolutely simple setup, almost to the point of being rediculous. Literally just plug it in, your Mac will detect it and ask you to enable Time Machine if it's not been enabled previously.
I happen to have bought a G-Tech, I like it because it's quiet, doesn't overheat, supports Firewire800 and I spent all of 2 minutes enabling Time Machine. So for alot of people new to Mac, it's the EASIEST solution plus G-Tech makes good products.
Not that guru skills are required for setting up a third party external HD, the advice given previously was excellent and easy enough to follow, but I suggest those not familiar with basic FDISK usage in the PC world (or lack basic Linux experience with mounting) would appreciate the plug and play.
-jim