By default, without a DNS server, windows can use NetBIOS (a Microsoft name resolution protocol) to discover the names of other windows systems local to their network. As mentioned in this answer, it looks like you need to setup SAMBA (or at least winbind) on the Linux side. Here is a basic set of instructions:
To enable Windows netbios name resolution from a Linux computer, make sure that Samba is installed (although the smb service does not need to be running). The Samba suite includes winbind, which enables Windows host names to be resolved. Then edit /etc/nsswitch.conf and change this line:
hosts: files dns
to this:
hosts: files dns wins
Then test by pinging the computer name of Windows machine on the LAN:
$ ping windowsbox
BTW, this has nothing to do directly with WINS. WINS is a NetBIOS server typically used in larger networks to cut down on broadcast traffic, provide a legacy centralized name resolution platform, and ultimately to enable systems on different networks to know each others' NetBIOS-name-to-IP mapping.
An alternative to SAMBA would be to setup a DNS server and ensure dynamic DNS updates are configured or that DHCP can register DNS records.