Update: Wheezy + dnsmasq + dnscrypt 2018-06-24
I have written up instructions for installing dnscrypt-proxy on Debian a few times, and frankly this older stuff is a bit inconsistent. You'll find my most recent instructions (tested on Jessie) here. I am just leaving this old stuff here for reference in case anyone wants to see more about dnsmasq I guess.
Update: Wheezy + dnsmasq + dnscrypt 2017-09-24
I have been slowly migrating posts from my old Wordpress site to this not-so-fancy site by checking which posts have been accessed on the old site and copying over the popular ones manually. There didn't really seem to be any posts getting hits lately so I was thinkin' of dropping the old site and moving the new one to https. Turns out this one started seeing some traffic lately. I can only assume that it has something to do with my recent addition to the dnscrypt public resolvers list, though it could be just luck. Frankly Wheezy is pretty outdated and I would suggest moving on to Jessie (assuming you can live with systemd). Seriously, Jessie + backports is probably the best way to go now.
Update: Wheezy + dnsmasq + dnscrypt 2015-10-27
Well, I switched over the mail server tonight. I was seeing URIBL_BLOCKED errors in my SpamAssassin headers and wanted to get rid of them. Here's hoping that (1) okturtles won't have this problem and (2) it'll work as well on the mail server as it did at home.
Wheezy + dnsmasq + dnscrypt 2015-09-08
DNS is the service that resolves names like www.xkcd.com in to IP addresses like 126.96.36.199. This is useful because it allows you to remember simple names instead of IP address. Most people probably use their home router as their DNS server, and it in turn likely uses their ISP's DNS servers to resolve names. Some people prefer to use Google's free public DNS servers or other free public servers because they figure it is faster or provides some kind of security. In practice these services are not faster, are typically less secure, and are almost certainly designed to track you.
Here at home I use a Debian Linux box as a caching DNS server because it gives me nifty advantages like blocking ads and malware, while not throwing data at confirmed trackers and DNS poisoners like Google & OpenDNS. It also means that when I make a change to my DNS it immediately affects all of the devices on my network (unless I inadvertently left a DNS caching service running on one of them). The problem is that there could still be DNS information disclosure. This doesn't mean that someone can see the content you are looking at, but it means they can tell which web sites you are visiting.
Because DNS is typically plain text, it means that there is a possibility your DNS queries could be "seen" and recorded. Someone on your wireless network might be able to capture them, or perhaps even your ISP captures the traffic right at their DNS servers. If you use Google or OpenDNS then you know they are recording the information. So what is the alternative? Well, the best I can see so far is dnscrypt. It encrypts your DNS traffic so others can't read it along the way. Unfortunately you still have to trust the person running the dnscrypt server that you are connecting to (but I guess this is going to be the case until we are all running root servers).
NOTE: one of the important things to understand about how my setup works, is that dnsmasq is still the DNS resolver on all other internal network devices. The dnsmasq server is setup to use dnscrypt as it's upstream resolver instead of your ISP or Google or whatever you currently use. dnscrypt then connects to whatever secure DNS server you tell it to on the command line (more on this later).
I found some instructions here and there on setting up dnscrypt (mostly here), but nothing that seemed to work perfectly with Debian Wheezy and dnsmasq. So here are the steps I ended up using to make it work.
Dependencies: I don't like sudo, but a lot of people seem to [incorrectly in my opinion] think that it is an absolute necessity... so this process is written (and tested) with the assumption that is how it is being performed. It also assumes that you are already running dnsmasq as a DNS server for your local network and that you are using a static IP address on this server. If you are not using sudo, kudos to you! If you are not using static IP addressing on your DNS server, you might want to think about it. Libsodium is a dependency that is downloaded as part of this process.
Begin by making sure that your DHCP client is not going to keep changing your /etc/resolv.conf file.
$ sudo apt-get remove isc-dhcp-client isc-dhcp-common
Confirm that you are in fact using a static IP address
iface eth0 inet static
Download and build libsodium and dnscrypt.$ mkdir ~/dload && cd ~/dload
$ wget https://download.libsodium.org/libsodium/releases/libsodium-1.0.3.tar.gz
$ mkdir ~/src && cd ~/src
$ tar zxpvf ~/dload/libsodium-1.0.3.tar.gz && cd libsodium-1.0.3
$ make && make check && sudo make install
$ sudo ldconfig
$ cd ~/dload
$ wget https://download.dnscrypt.org/dnscrypt-proxy/dnscrypt-proxy-1.6.0.tar.gz
$ cd ~/src
$ tar zxpvf ~/dload/dnscrypt-proxy-1.6.0.tar.gz && cd dnscrypt-proxy-1.6.0
$ make && make check && sudo make install
Modify dnsmasq so that it binds to your 127.0.0.1 address but not the rest of the 127.0.0.0/8 addresses, and set your upstream resolver to dnscrypt (which is going to be listening on 127.0.0.2).
Edit your /etc/dnsmasq.conf file Uncomment "bind-interfaces"
$ echo "nameserver 127.0.0.2" | sudo tee /etc/resolv.conf
Set dnscrypt to run at boot time
$ sudo crontab -e @reboot /usr/local/sbin/dnscrypt-proxy -a 127.0.0.2:53 -d -R dnscrypt.eu-nl
Now you could just start dnscrypt by running sudo /usr/local/sbin/dnscrypt-proxy -a 127.0.0.2:53 -d -R dnscrypt.eu-nl, but I would suggest rebooting which will ensure that it is starting properly on reboot. You may also change the server designation at the end of the crontab'ed command to switch which upstream server you wish to use. My example of dnscrypt.eu Netherlands should be fine but you may wish to choose another from the list which can be found at /usr/local/share/dnscrypt-proxy/dnscrypt-resolvers.csv. It looks like Fusl certainly has quite a comprehensive list of geographically diverse servers, but I seemed to have trouble getting certificates from them. I tried okturtles which seemed to work well, and I like the look of what seems to be their motivation. I'm not quite ready to put my live mail server behind dnscrypt yet, but I am pretty sure that I will after some testing at home.