What do I put in the "Search Domains" field?

More accurately: It's a list of domains that the DNS resolver will append to a hostname when attempting to resolve it to an IP address.

For example, let's say you manager a bunch of servers at mycompany.com (web1.mycompany.com, web2.mycompany.com, db.mycompany.com, etc), and you're tired of typing the fully-qualified domain name every time you need to ping them or SSH to them.

You can add "mycompany.com" to the list of search domains to avoid that. Now when you ping or SSH to web1, it will try to resolve web1, fail, then try web1.mycompany.com, which will succeed.

If you connect to a domain server at work with a number of other servers connected to it you would put the names of the other servers you wish to search in this field.

The average user connecting to their ISP would leave this field blank.

The following Ubuntu Forums post explains it in more detail