Can Time Machine back up to an external HD connected to another Mac?
Yes. I've been doing this since Snow Leopard. All my MacBook Pros in the house do their Time Machine backups to an external USB drive that's hanging off an iMac running the standard OS X install (i.e. not Server). At the time of writing the iMac has been upgraded to Lion as has one of the MacBook Pros.

First, configure your target machine (the one with the USB drive attached):


Format the drive as OS X Extended Journaled. Give it a useful name. I use 'Remote Backups'.
Go to System Preferences -> Sharing
Make sure File Sharing is turned on and has a check mark next to it
Under the 'Shared Folders' list click the + button and add your newly formatted USB drive to the list of shared folders
Select the drive in the list and under 'Users' make sure everyone shown has read/write access to the drive.


Now you need to configure your source machine (the one you want to keep it's Time Machine volume on this drive):


Open Finder on the machine. Find your target machine and click on it. Mount the drive on this machine.

If you're asked for a user name and password use the user name and password on your target machine that you used to login and setup the share. Make sure you save this user name and password to your keychain

Go to System Preferences -> Time Machine
Click Select Disk...
The list should include the mounted drive, select that. Pick your encryption options and hit the Use Backup Disk button


You're now all set up to use this remote drive as your Time Machine backup location. When Time Machine runs you'll see this drive appear as a mount on your system, and when it's done the mount will go away.

If you browse this drive from the target machine you'll see sparsebundle files, one for each machine that's doing a Time Machine backup to this drive, on the disk. These are the actual "disks" that Time Machine is using on each machine to keep the incrementals. If you click on one, it should mount and you should be able to browse it like normal.

If you have a complete disaster and need to do a fresh OS X install and recover from Time Machine you can point the recovery process at the remote drive and it will ask you to pick a sparsebundle from the drive to recover from. Or, and this is what I recommend, you can unattach the drive from your target and attach it via USB to your machine and do the restore over USB which is much faster.

I can confirm that complete restores from Time Machine backups kept in this manner work well. I've had to do two of them in the past few years on machines that keep their backups this way and both went smashingly well. Browsing Time Machine history in the Time Machine viewer can be a bit laggy, but it does work.