They do NOT have to be on separate partitions. You can have OS X and OS 9 reside on the same partition if you like, or on separate partitions.
If you install OS X first, be sure to click the checkbox "Include OS 9 drivers" when you format the drive. Without these drivers, you will not be able to install OS 9 on the same drive as OS X. There is no way to add the OS 9 drivers later if you forget this step -- you must initially format with them, or re-format to get OS 9 drivers on there.
Also, be sure to format in HFS+ format (not plain HFS), as OS X requires the HFS+ format.
That being said, to prevent any hiccups along the way, I recommend installing OS 9 first (to make sure you've got OS 9 drivers on the drive), then install OS X.