Debian packages install
Install Daemontools and ucspi-tcp
aptitude install ucspi-tcp daemontools daemontools-run
Install Courier packages
aptitude install courier-base courier-authdaemon courier-authlib courier-authlib-mysql courier-imap courier-imap-ssl courier-pop-ssl courier-pop courierpassd courier-maildrop gamin
You should accept all the default answers
Install needed compiler, tools and library
aptitude install cpp g++ gcc make automake wget telnet libtool patch patchutils logrotate dh-make-perl libltdl7 equivs expect openssl libssl-dev libgmp3-dev libgdbm-dev libpcre++-dev libpcre-ocaml libpcre-ocaml-dev
For security reason, it's a good idea to remove the compilers (cpp, g++, gcc and make) after your complete this guide
Install MySQL database and libraries
aptitude install mysql-common mysql-server-5.1 mysql-client-5.1 mysql-server-core-5.1 libmysqlclient16 libmysqlclient-dev
Remember your root MySQL password (described as MySQL_root_password later in this guide)
Install Apache & PHP
aptitude install apache2 php5 php5-common libapache2-mod-php5 php5-mysql
Accept the default proposal about apache2-mpm-worker
Install antispam and antivirus
aptitude install spamassassin spamc pyzor razor clamav clamav-daemon clamav-docs
Install un-archiver tools
aptitude install arj unrar lha unzip bzip2 tar tnef
Install perl modules
aptitude install perl-suid spf-tools-perl libmailtools-perl libnet-cidr-lite-perl libnet-daemon-perl libtest-distribution-perl libmail-spf-perl libperl-dev
aptitude install libhtml-format-perl libhtml-parser-perl libhtml-tagset-perl libhtml-tree-perl perl-doc libdate-manip-perl libio-string-perl libio-socket-ssl-perl libnet-ident-perl libsys-syslog-perl libencode-detect-perl
aptitude install libnet-dns-perl libplrpc-perl libtimedate-perl libcompress-zlib-perl libdigest-hmac-perl libdigest-sha1-perl libparse-syslog-perl libmail-dkim-perl libcrypt-openssl-bignum-perl
aptitude install libhtml-format-perl libhtml-parser-perl libhtml-tagset-perl libhtml-tree-perl perl-doc libdate-manip-perl libio-string-perl libio-socket-ssl-perl libnet-ident-perl libsys-syslog-perl libencode-detect-perl
aptitude install libnet-dns-perl libplrpc-perl libtimedate-perl libcompress-zlib-perl libdigest-hmac-perl libdigest-sha1-perl libparse-syslog-perl libmail-dkim-perl libcrypt-openssl-bignum-perl
Install debug / manipulation tools
Those last ones are not mandatory but are useful if you need to debug
aptitude install dnsutils whois findutils pciutils less net-tools tcpdump iptraf dstat iotop mc locate
Download all the needed items for the Qmail installation
Users comments
If you're installing on LUCID, check http://ubuntuforums.org/showthread.php?t=1458885 for installing libmd5-perl. (post #4)