Out of the box, when Red Hat Enterprise Linux requests a DHCP address, it doesn't send up a hostname for a dynamic DNS server to use.
It is simple, but seemingly different on each distribution. But for Red Hat Enterprise Linux, create a file /etc/dhclient-eth0.conf (or /etc/dhclient-eth1.conf for eth1, etc) and put this in it:
send host-name "yourhostname";
Of course, you can put other options for dhclient in there too.
If you poke around in /etc/sysconfig/network-scripts/ifup you'll see how it is used.
Looking for how to do this for Debian/Sarge? Look here