Well, I'm on linux and running dhcpd so I added the following lines to
my /etc/dhcpd.conf:

option routers 192.168.1.1;

option domain-name-servers 192.168.1.100;

I'm running a dns cache on 192.168.1.100, and I'm behind a firewall/router at 192.168.1.1 (hence the 192.168.x.x addresses). Similar options exist in udhcpd (another dhcp server I didn't have as much luck with) and I'm sure other dhcp servers.