Install Windows first, then Linux. Linux usually provides tools for partioning during the installation. Some, as Mandrake Linux, can even resize NTFS partitions.
An anternative way could be to create Linux partitions from Windows. A tool that can do that is PQ partition magic, but it ain't free.
It should be very straight forward though: Install Windows as you usually do. While installing Windows you can left some space unformated to use later with Linux, but this step is not necessary. Then boot from a Linux CD and install Linux. That's pretty much it.
Good luck!
P.S: in the future, try explaing a little better what exactly did not work and what you did. Just saying "it did not work" as you said isn't much of help
