I have two Debian servers, One is the old one, running on hardware that dell is no longer supporting (without us shelling out again) in a couple months. The other -- the new one-- is a virtual instance I have just installed on top of Citrix XenServer. Both are running Debian 4.0 "Etch". 

The application we have running on the old server has quite a few dependencies, and the Operating system hasn't been re-installed in quite some time. As a matter of fact, it is running an image which was based off an image which was based off an image.  In other words, I needed a quick and dirty way of installing all the packages which are needed on the new server, without using the old image.

Here's what I did:

First, on both servers I made a list of the packages which were installed. I did this by running the command:

root@oldhost # dpkg -l > packages.old

and on the new server:

root@newserver # dpkg -l > packages.new

I then combined the lists using text tools such as 'cat' 'sort' 'uniq' etc...
Then I used vimdiff to find the differences between the two servers and make choices as to which packages I wanted installed.  All in all I ended up with a third list which was my cleaned list of packages.

After copying the clean list to the new server, I ran this command:

perl-01:/tmp# for i in `cat packages.final` ; do dpkg -l $i &>/dev/null && echo "found package: $i, doing nothing" || apt-get install $i; done

This command will install a package if it's not currently on the system, and output "found package $foo, doing nothing" if it is already installed. You have only to sit at the prompt and answer any of the dpkg-configure questions which may pop up.

Cool, no?