Ridiculously easy. OK, it's not as easy as right-clicking the drive and selecting "Format" as you would in Windows (one of about 5 things Microsoft does better), but the above poster pretty much points out everything about it. Takes maybe a minute to format.
If you buy a HDD from a company you've actually heard of (Western Digital, Seagate, Maxtor), you'll have no problem getting it to work. I stick with WD drives myself, but most of the big boys work fine with Macs.