Debian packages nice to have for Drupal 6 local dev workstations

apt-get install mysql-server mysql-common mysql-admin mysql-query-browser apache2 php5 php5-cli php5-common php5-mysql php5-gd php-apc

For servers, you only need
apt-get install apache2 php5-mysql php5 mysql-server mysql-common php-apc php5-gd php5-cli (for drush)

other things that you might want:
openssh-server (for remote servers)
cvs (for systems that will be retrieving packages from drupal.org)
subversion [or] git-core (better version control for everything else)

Then for clean urls, make sure AllowOverride All is set in directory definitions. Then enable mod rewrite:
a2enmod rewrite