What exactly are they after? A way to determine the host's name when
logged in on that machine?

As in:

jbuchana@flenser$ hostname
flenser
jbuchana@flenser$

Or is it something else?

Yup. Thats it.. but they are seeing this through their internal router.
All computers are inspected, mac addr are recorded, and all pc's must be
identified on the network. I just cant figure out how to get my computer
to identify itself.

I may be wrong here, but I think all that they can get directly
scanning the machines on the network is the IP addresses. To resolve
those into names, I believe that they have to query the a DNS server
or look in their local "hosts" file (Windows has one too, but it is
buried rather deeply).

Getting them to add your machines to their DNS or hosts files may be
easy, or it may be hard, depending on their attitudes.

On my own network, none of my ubuntu machines show up with a host name like the
Windows machines do. They show up at s * only.

For example:

Mad-Max 192.168.1.103 00:00:00:00:00:00
* 192.168.1.104 11:11:11:11:11:11

Where * is the ubuntu machine.

On 8.04 I went into networking and could name the machine there. That option is
no longer available. Though my machine is accessible though the url
http://madmax/filename etc, ... which I have set up for the normal development
purposes.

Unix machines don't normally broadcast their hostnames across the lan.
That's a peecee-lan thing. If they want your unix hostname to show up in
the peecee-lan listings, then you'll have to have samba installed and
have the smbd and nmbd daemons running.

Then they will broadcast whatever hostname your system has. If you want
to force the hostname to be a certain value, it can be set in
/etc/samba/smb.conf - perhaps that adjustment can be made via some GUI
control if you have samba and friends installed, I'm not sure. But the
file edit works directly

Under the [global] section you can set the visible peecee-lan hostname
like so:

netbios name = MULHOLLAND

Restart the samba services after modifying smb.conf