you could hook the printer up to the router, if your router supports it
if you leave it on the linux box ... you will ... need (trying to remember) ... set the computer up as a print server ... cups? should do it ...
alternatively if you hook it to the XP box, you'd use samba.
i just googled linux print server and it gave me :
so samba might be the way afterall. i noticed that it is aimed at 95/98 ... but the only difference is how you create a windows user for the most part, which ... shouldn't be a problem i think.
considering the distro's you're running there (debian and knoppix) you shouldn't have too many worries to get it working. though debian would possibly be more straight forward.
As to why it's such a pain, well ... i think doing anything you don't know how to do is initially difficult.