When backing up many Macs to one hard drive, must the hard drive be partitioned for each Mac?
If you want the partitions to be bootable, yes you will need a separate partition for each mac you're backing up. The only way to have multiple backups in the same partition is to separate them out into other directories, which is not something most (all?) computers will be able to handle when trying to boot.

If you use Time Machine to do your backups, you could back them all up to the same partition. Then while the partition is not bootable, when you boot into recovery on the given mac, you can point at the drive and Time Machine will distinguish between the various backups.

The final, most convoluted option could be to use Read/Write disk images, those could be mounted, and backed up to, and then if a system failed, you could directly image the disk image to the new drive. This doesn't buy you a whole lot over backing up to separate folders and just copying the contents of that folder over to a new drive, so I wouldn't really bother with it.