Linux machine not reporting hostname correctly
So I have a linux machine that I'd like to report its hostname correctly so it can be identified on a list of machines connected to my network.
I have /etc/hostname set and hostname correctly reports what it is. But it seems not to report this to other machines that ask for it.
For example, the command nslookup <my ip> reports NXDOMAIN basically meaning, from what I gather, that it couldn't find a hostname. Yet when I run nslookup <other windows machine ip> it correctly reports the hostname for the Windows machine.
What do I need to set up in order to have it be identifiable by its hostname? Do I need a DNS server and does Windows automatically run one?