Depending on how much your budget is, I would recommend the following:
1. 1 drive for each machine. Label them so you don't get them mixed up.
2. Each drive being at least 2x the size of the drive you are backing up.
The drives will fill up eventually. before it does, Time Machine will notify you that it will be writing over the oldest backup files. I just had a 1TB drive flip for my 500gb MBP drive. No biggie, I let it continue on.
Now, if you want to use a drive that will be connected to a network and give you plenty of room, I would look into a Western Digital My Book Live. It will plug into your router and can be used for multiple Time Machine backups. I have a friend who has one for 3 machines, with the drive set up with 3 partitions of 1 TB each. This is done on the drive, not the computer - do not let the Mac format the drive. The drive has a web interface to configure it. I have one of these drives, but do not use it for Time Machine, I use it for network storage with 4 different shares set up. You could get the 3TB model, set up 2 1TB paritions for your MacBooks' TM's and still have 1TB for network storage. The problem with this is that if the WD drive goes bad, you lose EVERYTHING in one shot.
I still recommend 1 and 2 that I mentioned at the start of the message.