On the Windows XP PC, share the printer to everyone including guest account, turn off your firewall, it will cause issues. Once it's working you can always go back and add exceptions...
On your linux PC, Assuming Gnome here, open System/Administration/Printing, Click "New Printer", select "Network Printer" then use select "Unix Printing LPD"
In the Host Field type the IP number of your Windows Print Server (ie 192.168.1.2)
In the Queue Field type the Share Name of the printer, we'll say "Laserjet 4" for now
Next page, manufacturer and model of your printer from the list, click apply.
That should be about it. I'm doing this from memory, I hope it works for you.