The trick is in knowing that Windows "printer drivers" are actually not true drivers. They convert the GDI commands to device-specific command sequences, which are then passed to the spooler, which in its turn invokes the "true" printer driver (typically the LPT device). Which is why it's freqently difficult-to-impossible to move a document from one printer's queue to another.
Actually, in NT, they do have an intermediate serialized GDI format, but I'm not sure if Linux has a converter for that or not. Usually Linux prefers to convert to PostScript.
Getting to the solution - you can either setup printcaps on the Linux machines specific to the target printer(s), and/or output to Postscript and route it to the Windows Postscript driver, if your printer(s) support that option. Graphics printing in Linux is usually done to PostScript, and in cases where the target printer doesn't speak PostScript, then converted from PostScript to device-specific.
I know, that doesn't make a bit of sense, but the key is that if you can get the Linux machine to print to the selected printer when it's locally attached, then
you should be able to print to the same printer over a network using Samba.