On Ubuntu and Debian you may find that changes to resolv.conf disappear from time-to-time. This is because you are not supposed to manually edit the resolv.conf file anymore. Various network pre-up and pre-down scripts can cause resolv.conf to be overwritten. This will usually happen after a reboot; when a network interface is brought up; or when dhclient renews a dhcp lease.
If you are running DHCP client
If you are running DHCP client then you can put static nameserver in either /etc/dhcp3/dhclient.conf or /etc/resolvconf/resolv.conf.d/base (follow the static address instructions below). If you use /etc/dhcp3/dhclient.conf then the changes will not persist if you switch to a static IP or another interface. In other words, the static nameservers in dhclient.conf will only appear when using DHCP. See DHCP for information on going that route.
If you are using Static IP
If you have a static address and your resolv.conf is lost on reboot then you need to create a file:
Add the nameserver lines that you want to always be included in your resolv.conf file. Then after no matter what service causes resolv.conf to be regenerated you can be sure it will contain these nameserver lines. For example, you might put the following in "base" to use OpenDNS:
nameserver 126.96.36.199 nameserver 188.8.131.52
Do a man on "resolvconf". This is not the same man page as "resolv.conf".