What factors are important when selecting an external hard drive for time machine backups?
The most important factor is get a drive as soon as you can and make sure it's always connected. Even the cheapest slow USB drive is so much better than none.
Get something that is built strong enough for your environment (for most it's sitting on a desk but is more a factor if you travel with the drive) and looks appropriate sitting by your mac.
Spend a little more money to buy a lot more space but don't break the bank on the biggest drive unless you really need it. I've been served well getting the lower end drives sold in the Apple stores (they tend to stock the best quality at decent prices) even if I don't actually buy it there. I usually get the middle sized drive and upgrade the size until the jump in price is $65+ for the next larger size.
I'll disagree on the necessity to get a certain speed interface or FireWire.
The only times you really notice a faster drive for backups is the first time you backup all your data and if you ever have to restore the drive.
TimeMachine runs in the background with low priority (incremental backups over the network get done promptly which is way slower than USB speeds). Your use of the mac isn't disturbed while the backup progresses, so only spend the extra $$ on a faster interface or fancy disk if you really need that speed in the event of a restore.
With my backups, I've been happy buying less expensive drives more often than I could if I bought the best. When the drive fills or 18 to 24 months pass, I "retire" that drive, putting it on the shelf for permanent storage. This keeps my backup drive fairly new and I have longer history if I need to go back to older files. If you intend to run the drive for 3+ years into the ground, then it's nice to spend another $25 to $150 or so on the best quality drives with a longer warranty.
Lastly, I would avoid any drives that are not a single unit. Raid increases the parts and size which is statistically less reliable. I prefer less chance of failure on my backup drive rather than a bigger bucket of backups.
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.