[SGVLUG] Naming Internet-in-a-Box service with DHCP

[Braddock]

Hi Guys,
Thanks for allowing me to present and experiment on you last week with 
the Internet-in-a-Box.

I have a question for the group.

The Wired Internet-in-a-Box device is a Debian NAS (hacked Seagate 
GoFlex Home) running a web server.

I want the install procedure on a network with an existing DHCP server 
to look like:

1) Plug into power
2) Plug into wired ethernet port
3) Turn on
4) From a web browser on any other computer or device on the network go 
to http://knowledge and access the device

This setup must be easy, I don't want the end user to have to configure 
a static IP.

How can I achieve this?

On my DD-WRT WRT54G it provides a name server proxy and picks up on the 
hostname when the DHCP request is made and resolves DNS queries for it.  
But this is fragile, and some devices don't seem to work.

Would I be able to cover most devices by using nmbd?  Is mdns well 
supported?

Ideas?  Advice?

Thanks,
Braddock