External hard-drive backup for two laptops

I'm on the verge of buying a new laptop for Kelly (probably an iBook, because I can't talk her into waiting a few months for the new Intel ones). We are long overdue for a backup solution. Unfortunately, my employer's online backup service (free to employees) is Windows-only, so we can't use that. My best bet is probably an external hard drive. The slightly tricky part is that I need to have this thing talk to two different laptops, but I can't attach it to a server because I don't have one (we have no place to set up a desktop computer and no real need for one). I've got three questions:

1. Any hardware vendors you prefer or avoid?
2. Any Mac/Unix backup utilities I should look at? (Commercial software is fine.)
3. If I'm only doing periodic backups (weekly or monthly), do I need to keep the drive powered on all the time or can I safely shut it down between backups? Being able to store it away from a power outlet would be a plus, but I'm not sure that's practical.