How can I discover the hostnames for all the machines on my lan?

Avahi tools

There also are tools from the Avahi package to list services.

• avahi-browse (from avahi-utils)
  Command line tool that browses the network for any services used by Avahi.

    avahi-browse -at
  

• avahi-discover
  Is a GUI to display all Avahi services available:

  

nbtscan

A good tool to scan all hostnames on a network is nbtscan.

$ nbtscan 192.168.1.0/24                                                                                                  
Doing NBT name scan for addresses from 192.168.1.0/24

IP address       NetBIOS Name     Server    User             MAC address      
------------------------------------------------------------------------------
192.168.1.0     Sendto failed: Permission denied
192.168.1.162    CLEMENTINA          <server>  CLEMENTINA          00:00:00:00:00:00
192.168.1.205    CLEMENTINA          <server>  CLEMENTINA          00:00:00:00:00:00
192.168.1.255   Sendto failed: Permission denied

• Note: This is for NetBIOS, not for mDNS.
• Official site

You can install it in the Software Center by searching for 'nbtscan', through their website, or via Terminal:

sudo apt-get install nbtscan