Update: Jessie+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: Jessie+dnsmasq+dnscrypt 2017-07-21
Just yesterday I tried this again on my Banana Pi M1 running Bananian and it worked just fine with dnscrypt-proxy v1.9.5 (the most recent as of today). I simply followed my own instructions below from 2017-03-30 and it went fine on the first try. Booyeah! :-)
Update: Jessie+dnsmasq+dnscrypt 2017-03-30
Because of occasional inconsistencies I had sort of let my dnscrypt use lapse. But recently I have been screwing around with it again, and in fact have been working on my own public dnscrypt resolver. During these efforts I have found some minor ways to streamline the install of dnscrypt-proxy on Jessie for use with dnsmasq. Here's the quick an' dirty:
# apt-get install build-essential libsodium-dev
# mkdir ~/src
# cd ~/src
# wget https://download.dnscrypt.org/dnscrypt-proxy/dnscrypt-proxy-1.9.4.tar.gz
# tar -xzvf dnscrypt-proxy-1.9.4.tar.gz
# cd dnscrypt-proxy-1.9.4
# ./configure
# make
# make install
Then modify your dnsmasq to uncomment the "bind-interfaces" line, and set your upstream resolver to 127.0.0.2:
/etc/dnsmasq.conf
bind-interfaces
server=127.0.0.2
Lastly, just like before, you crontab it the proxy to run at boot:
# crontab -e @reboot /usr/local/sbin/dnscrypt-proxy -a 127.0.0.2:53 -d -R okturtles
If you want to use a custom dnscrypt resolver (like mine or your own for example) you can use full command line options to specify the needed info like this:
@reboot /usr/local/sbin/dnscrypt-proxy --local-address=127.0.0.2:53 --resolver-address=64.137.211.225:443 --provider-name=2.dnscrypt-cert.snork.ca --provider-key=CF29:ECC5:C7CF:C98C:8356:3574:5AE4:177D:7DB1:B4AA:2503:391B:861B:4C98:E0D8:B8CA
Now, start up your proxy by manually typing in the command you crontab'ed above, and restart dnsmasq systemctl restart dnsmasq.service to see if you got it working.
Update: Jessie+dnsmasq+dnscrypt 2016-09-09
This was not working on my Banana Pi, I was getting an "Unable to bind" error message in my syslog and found this issue that describes exactly these symptoms. I simply did what lamixer said and installed v1.6.0 right over top of 1.7.0 and it started working just fine. Sadly the issue was just closed without any further input, which means this may not get repaired on Bananian and similar distros. :-(
Jessie+dnsmasq+dnscrypt 2016-09-09
About 366 days ago I setup Debian Wheezy with dnsmasq and dnscrypt because I don't like the idea of someone (my ISP) storing and potentially disclosing my DNS queries. I don't like the idea of using Google for my DNS queries since they are even more likely to share that information. And I don't like using OpenDNS for my queries because they have already been found to be poisoning DNS for their own benefit. Anyways, I ran this for a while, even on the email server, and the minor little resolution issues eventually sent me back to Teksavvy for my queries.

Somewhat recently I have been trying out dns.watch as my resolvers but in the last week or two have noticed that whois.com domain queries do not complete. No NXDOMAIN reply, just a timeout. I thought at first it must be a problem with my network, but I even had a friend test it out and he has the same problem. Now it appears as though whois.com may have some minor DNS issues, but it is nothing that should keep it from resolving. I sent an email to dns.watch to let them know of the problem but the email address they provide on their web site does not really appear to be a support address and I am a little skeptical that they'll reply. In the meantime I thought that maybe I should go looking for a new DNS solution.
I looked around for some free public DNS server adresses but didn't really find anything I like. I would have been okay with falling back to Teksavvy's servers but they do not allow non-Teksavvy addresses to use their resolvers and that would leave the mail server out of the loop. So, I am trying dnscrypt again... not only that, but I am trying okturtles again. Here's the updated instructions for Jessie, and written from the perspective of root (rather than a user who has to constantly use sudo to perform most actions). It also assumes that you are already using dnsmasq and are simply adding dnscrypt to it.
Remove unnecessary DHCP client software.
# apt-get remove isc-dhcp-client isc-dhcp-common
Install the software required for building source.
# apt-get install build-essential
Make sure your IP is statically assigned in /etc/network/interfaces
iface eth0 inet static
address 192.168.1.123
netmask 255.255.255.0
gateway 192.168.1.1
Download libsodium (dependency). At the time of this article, v1.0.11 is the most recent version, you should check to make sure that you are using whatever is recent when you perform these steps.
# mkdir ~/dload
# cd ~/dload
# wget https://download.libsodium.org/libsodium/releases/libsodium-1.0.11.tar.gz
Now build libsodium
# mkdir ~/src
# cd ~/src
# tar zxpvf ~/dload/libsodium-1.0.11.tar.gz
# cd libsodium-1.0.11
# ./configure
# make
# make check
# make install
# cd ~/src
# ldconfig
And now for dnscrypt (again, check that you are using the most recent version).
# cd ~/dload
# wget https://download.dnscrypt.org/dnscrypt-proxy/dnscrypt-proxy-1.7.0.tar.gz
# cd ~/src
# tar zxpvf ~/dload/dnscrypt-proxy-1.7.0.tar.gz
# cd dnscrypt-proxy-1.7.0/
# ./configure
# make
# make check
# make install
Edit your /etc/dnsmasq.conf and uncomment the line that says
bind-interfaces
This will mean that dnsmasq will be listening on 127.0.0.1 instead of 127.0.0.0/8 which is needed because the dnscrypt proxy will be listening on 127.0.0.2.
Modify your /etc/resolv.conf to say
nameserver 127.0.0.2
This will tell dnsmasq to use the dnscrypt proxy.
Now, run
# crontab -e
and add a line that runs the dnscrypt proxy on reboot. Like so:
@reboot /usr/local/sbin/dnscrypt-proxy -a 127.0.0.2:53 -d -R okturtles
As mentioned in the previous Wheezy-based instructions, it is possible to just start the dnscrypt proxy manually at this point, but it is better to do the reboot so you can confirm it will start automatically when the server is subsequently rebooted.