the actual order is paritition then format... but neways
the winxp cd should be bootable, meaning if you can go into your bios and change the boot order to boot off the cd first, it should boot right into the windows setup. from there, you can delete an existing partition (if one exists) or create a new one (it tells you how to do this in the setup). once its created, it will then prompt you if you want to format it. say yes and once the format is done, the install will continue and you're on your way.
hope this helps