I searched for it and haven't found it.. Is it possible to make DNSmasq automatically have the hostnames from it's DHCP clients? So if I have 4 system getting their IP's from it, I can go to another system and ping it by it's host name and it will automagically resolve for me without me having to do any work?

It's already setup like that; all the dhcp hosts are added to the .lan domain.

FYI: on a windows network, the auto-magical name resolution is facilitated by the windows networking services and the name resolution stacks.

For example, my home systems are all reachable through my non-WRT router via their respective names. With my linux file server, this ONLY works when the nmbd service is active..

Following mbm's suggestion, you could just add "lan" to the domain search order so that it checks 'compname.lan' automatically during any name resolution. I believe a quick addition to the dnsmasq conf file will do the trick for your DHCP configured systems. This solution is more universal, because it doesn't rely on NetBIOS naming services.