On OS X,
join the workgroup "WORKGROUP" - no WINS server is required (see the link for details on how to do it).
On Linux, you have to
edit the file /etc/samba/smb.conf - that link will aid you quite nicely. Change the workgroup line to "workgroup = WORKGROUP" and then alter any other configurations you want. I recommend you download and install Smb4k (if it isn't already) - it's a pretty Samba network browser, so that'll make connecting to your Mac much easier.
Best of luck,
-jk
Ps. I advise you ugrade to a newer distro (like Mandriva 2006) which brings newer applications and is easier to configure? I know Mandriva 2006 is a breeze to set up. Just my opinion