How can I determine the hostname of another machine on the local network? I am trying to set up an Android SSH client to connect to another machine on my local network. I can connect if I use the IP address, but the IP address can change. How can I determine the hostname that my Android device assigns to the other machine, so that I can connect using that instead?

(Right now the specifics happen to be using JuiceSSH to connect to an Ubuntu 13.10 laptop running sshd and mosh-server, but I'd like to learn a general approach that is not client or target specific. Ideally, a system-level Android command.)
For that, you'd need a local DNS server on your local network, which gets updated by the DHCP server assigning the IP to that machine (many routers offer this feature).

You can then tell your Android device to use that DNS as primary when connected to your WiFi network, while leaving the secondary as-is (so the latter would still resolve everything outside your network). This option is located in the WiFi APN settings: Long-press the entry for your home WiFi, select to edit it, enable "advanced options".