From the CCC site:
Macs can only boot from hard drives partitioned with either the Apple Partition Map (APM) scheme (PowerPC-based Macs) or the GUID Partition Table (GPT) scheme (Intel-based Macs). The hard drive icons that you see in the Finder are volumes. The partition scheme of a hard drive describes how volumes are physically defined on the hard disk. Every hard drive has exactly one partition scheme and at least one volume. When you "partition" a hard drive, you simply create multiple volumes on that hard drive.
Follow these steps to format your hard drive as an HFS+ volume:
1. Launch Disk Utility
2. Click on the hard drive device in the list on the left (the volumes have names that you see in the Finder, like "Macintosh HD" whereas the hard drive device has a name that includes the size of the hard drive and a vendor name or serial number, like "111.8 GB ST9129876A")
3. Click on the Partition tab
4. Choose "1 Partition" from the "Volume Scheme" popup menu (or more if desired).
5. Click on the "Options" button at the bottom of the partitions table and choose a partition scheme appropriate for the way you intend to use the hard drive (APM for PowerPC Macs, GPT for Intel-based Macs), then click the "OK" button:
Disk Utility Partition formatting options
6. Provide a name for your volume that will allow you to easily identify it as a backup volume.
7. Specify "Mac OS Extended (Journaled)" as the volume format.
8. Click on the "Apply" button
Because the 500gb you're buying probably is less than the sum of your two machines, just plan to partition it accordingly.
Joe