[CentOS] How to make nodes in my local LAN see each other's names

Hello

Sorry for the (I guess) simple question, but:

I have 7 computers under one 8-port router (D-Link DIR-100, firmware 
v1.13EU) in my network (actually in a sub-network) and they do not see 
each other's host names.

The router has the 'DNS relay' option enabled, and all 7 computers use 
the router as the DNS server, which in turn will forward DNS requests to 
the ISP DNS server. That way I can understand that simple, plain, 
default DNS is not enough for my boxes to see each-other's names.

Windows has a nice (or not) way to resolve the problem: CIFS (Samba) 
server names are automatically included in the name resolving procedure. 
I know I can do the same with my CentOS boxes if I install samba on each 
of them and add 'wins' to the 'hosts: ' line in /etc/nsswitch.conf, but 
somehow I think installing cifs on every node just to get my local 
machine names to resolve properly to the IP addresses is not the right 
way to solve my problem ...

What is the way to have all computers in my simple network know each 
other by name ?

Is it possible to have the name resolving procedure used by the system 
automatically recognize a new machine added to my network, when I try to 
access it with right host name, like WINS can ?

Also, I hear Linux does not have, by default, a cache of resolved names 
(like Windows does), and I find that to be a sad thing. Why should the 
default be set so that I contact the ISP DNS server for each and every 
web page I hit ?

Is there an easy way to install a caching name server on my each 
machine, and make sure my system is using /that server/ to resolve names ?

Thank you,
Timothy Madden