A DNS tunnel is a way to tunnel almost everything (Internet protocols) over DNS/Nameservers. On the connection you want to use a DNS tunnel you only need to have a recursive DNS server on port 53 available. So it even works on many commercial Wi-Fi hotspots without the need to pay. The fact that you are using such a DNS tunnel is very hard to detect for the owner of the network. A ICMP tunnel works similar to a DNS tunnel.
Because you "abuse" the DNS system for something it was not invented, it only allows a very slow connection of about 3 kB/s which is even less than the speed of an old analog modem. Thats not enough for YouTube or Filesharing, but should be sufficient for Instant Messengers like ICQ or MSN Messenger and also for E-mail.
The main problem is that there are no public modified nameservers which you can use. You have to set up your own one. You need a server with a permanent connection to the "free" Internet running Linux.
Implementations of DNS tunnels:
- Covert Channels inside DNS, a presentation by Lucas Nussbaum with comparison of OzymanDNS, iodine, NSTX and TUNS
- wiki.hackerboard.de on DNS-Tunnel (in German)
- DNS Tunnel client - A software to test if a DNS tunnel is possible
- EditDNS - A free DNS service which supports NS records for a DNS tunnel
- DNS6 - A free DNS service which supports NS records for a DNS tunnel