First, make sure Bind is not installed:

aptitude remove bind9 bind9-doc

Then install the PowerDNS server and the MySQL backend:

aptitude install pdns-server pdns-backend-mysql

Now create an emepty MySQL database and user with priviledges to access that database.

Then import the MySQL schema shipped with PowerDNS:

mysql -h db.example.com -u username -p powerdns < /usr/share/doc/pdns-backend-mysql/mysql.sql

Configure your database settings:

/etc/power-dns/pdns.d/pdns.local

gmysql-host=db.example.com
gmysql-port=3306
gmysql-dbname=powerdns
gmysql-user=powerdns
gmysql-password=password
#gmysql-socket=

Configure PowerDNS as shown below:

/etc/power-dns/pdns.conf

launch=gmysql
allow-recursion=127.0.0.1, 1.2.3.4, 5.6.7.8
local-address=1.2.3.4
out-of-zone-additional-processing=yes

Then finally restart PowerDNS:

/etc/init.d/pdns restart

Check syslog for errors then populate your database and test.

Install the PowerDNS recursor:

aptitude install pdns-recursor

Then configure the PowerDNS recursive server settings:

/etc/powerdns/recursor.conf

allow-from=127.0.0.1
local-address=127.0.0.1
local-port=53

Then reconfigure the PowerDNS server to pass recursive lookups through to your recursive server:

/etc/power-dns/pdns.conf

recursor=127.0.0.1

Finally restart pdns and pdns-recursor:

/etc/init.d/pdns restart
/etc/init.d/pdns-recursor restart

There's currently no Debian package, so download the latest source and unzip:

wget http://www.iguanadons.net/downloads/PDNS-Admin-113-11
tar zxvf PDNS-Admin-113-11

Now you should configure a virtual host and then follow web-based installer. Remember to delete the install directory!

You can use the zone2sql utility shipped with PowerDNS to import your existing Bind zone files to your MySQL database. You'll need a copy of your named.conf.local file and your zone files for it to import from:

zone2sql --named-conf=/etc/bind/named.conf.local --gmysql > ~/zone2sql.sql
mysql -h db.example.com -u username -p powerdns < ~/zone2sql.sql