I usually did this partly by using the Windows XP installation program and then the Fedora installer - not sure how this will translate to the Ubuntu installer.
Basically, step for step, I did this - note this is a DESTRUCTIVE approach and you'll loose everything on the machine's HDD! I'm aware this is not what you asked (you want to preserve XP) but it might give you an idea or help you get started, at least conceptually:
1. Format the machine's HDD and remove all partitions.
2. Boot from XP installation CD.
3. When you are asked to create / select partitions, create 3 - one for Windows XP, one for your Linux installation, and one for Linux Swap.
4. Size the partitions appropriately - e. g. have the Linux Swap partition be at least twice your physical RAM, and the Linux partition itself at least a few GB's.
5. Install Windows XP into one of the "big" partitions.
6. Once it is installed, pop in the Linux install CD.
7. If you can, select a manual partitioning scheme. Fedora has DiskDruid to do this automagically, I've never used it.
8. Select the large partition as your / partition.
9. Select the remaining "small" partition as your swap partition.
10. Format as advised by the Linux install program (the big partition to ext4 and the swap partition to "swap" format.)
11. When asked to install the bootloader (usually GRUB, but maybe lilo in your case) choose the "boot sector on root partition" (or your Ubuntu equivalent.)
12. You should see a screen where you can then choose which operating system will be started by default.
13. Complete the Linux installation and bootloader installation.
What should now happen if you reboot is that a menu will come up after the BIOS and POST (power-on self test) which will allow you to choose to boot Windows or Linux.
Note that if you ever re-install windows after installing Linux, the bootloader option menu will not appear when you reboot the computer. This will be because Windows will have overwritten GRUB / lilo in the bootsector of the HDD. In such a situation you'll need to use your Linux rescue disc, but that is beyond the scope of your question - just take note.
Hope this helps.