I'd love to see proper Avahi support in the Nokia N800 (just think of proper file manager integration of announced WebDAV shares!), but until now Nokia doesn't ship Avahi in Maemo. However, there's now a simple way to install at least basic Avahi support on the N800. The INdT includes Avahi in their Canola builds. Hence: just install Canola and your N800 will register itself via mDNS on your network.
In related news: I am happy to see that Avahi has apparently been included in the just announced GNOME Embedded Platform.