Hey thanks very much for the links, maroonbaboon! (why couldn't I find those?)
Anyway, I'm happy to hear that OS X can deal with CUPS directly and bypass Samba. But I still can't quite crack it. I see that others are able to just plug a Mac into their network and other printers on the network just appear like magic. So maybe it's CUPS on my Linux box that isn't broadcasting.
If I go to http://localhost:631
-- shouldn't I see some sort of CUPS admin thingy? I just get "resource not found on this server". Could that be why my Mac can't see it?
Just stabbing in the dark now... any ideas anyone?