I have XP on my first hard drive and Linux on my second. The Linux boot program (either GRUB or LILO) will happily boot both.
Linux can be on any partition.
I don't know if the Linux partitions HAVE to be primary, but mine are. Just about all Linux distros can sort their own partitions out, however, so you don't really need to worry.
You might get a better answer if you click here