If you don't have Samba, you need it to connect to a printer on a Windows machine.
Try running smbclient
as root from a terminal in the Linux machine. It should tell you how the share is being seen by the Linux computer and give you the information you need to install the computer as a network printer in CUPS. I'm not sure, but smbd (Samba daemon) may need to be running for smbclient to work. I've never tried smbclient without smbd running.
If it's an HP printer, install HPLIP
. Make sure you also install the HPLIP GUI (how to do that depends on your distro). Run HPLIP and tell it to look for a networked printer.