The printer on the Ubuntu box needs to be shared. The gnome printer administrations GUI tools are sufficient for this. Just enable the two network sharing and printer detection options.
Test from the Mac whether you can see the cups system on the Ubuntu machine: Open Safari at http://myubuntuhost:631. If you can see your printer. If not your Ubuntu printer is not working even on the Ubuntu system.
Since I upgraded to Leopard I could not see/access/configure the remote printer in any way, until I read the page linked above and made the following chnages:
On the Mac side, add/change these lines in the file /etc/cups/cupsd.conf:
Then reboot the Mac.
Now when you try to print something you may notice that all your printers are gone on the Mac. But when I tried to select a printer a new printer was automagically added after a few seconds. The new printer had the name MYPRINTER @ MYMACHINE so it is easy to recognize whether this worked or not.