Partitioning your system before installing Windows
One of the first steps of a Linux installation is making place for your Windows. This step is called repartitioning. Usually this step is integrated into your Linux's distribution installation, sometimes it is not. Here there are some clues about how to repartition some systems before actually installing Gnu/Linux.
If you want to resize your Windows 9x (or any other Windows version that do not need specil tricks) you can just take a look at: Gparted Documentation - HOW TO RESIZE PARTITION.
What it is special about Windows XP is that it stores its system files at the end of its partition. When Windows XP was released I realised that I could not repartition my Windows XP partition after defragmenting it because there were still these files at the end of its partition.
I think that nowadays you can defrag and resize (without loosing any data) your Windows XP partition with Gparted Live CD however I have not confirmed this assumtion with an actual installation yet. I also wonder myself if Ubuntu's installation can defrag and resize (without loosing any data) your Windows XP partition.
One thing that you should know if that if you have ntfs (99% of the times) you will have to resize the ntfs partition and just after that boot into Windows. You will have to wait for some strange checks and wait for login screen. After login screen you can reboot. After this point you can safely modify the ntfs partition contents.
Vista partition size
Vista special trick is its size knowledge. Vista knows what's its exact size. If Vista detects after a reboot that its stored partition size does not correspond to the actual partition size it just stops booting.
However if you use programs such as the Vista Disk Management tool which can update that stored partition size you will not have any problem.
Vista Disk Management
You can use Windows Vista's own Disk Management tool as described in Vista Rewired - How to resize a partition in Windows Vista.
Gparted Live CD
As I have already said you using Gparted does not update the stored size. However you can fix that later. In howtogeek.com - Using GParted to Resize Your Windows Vista Partition they explain how to resize your Windows partition with Gparted Live CD and how to fix the Windows boot afterwards. You will need a Windows Vista installation dvd for that.