Restoring all data and dependencies from dpkg --set-selections '*'

Backup:

apt-mark showauto > pkgs_auto.lst
apt-mark showmanual > pkgs_manual.lst

Restore:

sudo apt-mark auto $(cat pkgs_auto.lst)
sudo apt-mark manual $(cat pkgs_manual.lst)

The selected answer to this question is incomplete and does not (or no longer) works. The painful fix is to use a bash for-loop to parse the output *.lst files and feed them to apt install. Bad choice, though, so will not be illustrated here.

A better choice is to use apt-clone, as seen in this answer on the Unix & Linux Stackexchange. This creates a small file (around 100K or less for my system). Allegedly, it will clone the packages with little effort or pain.

So, in short, on the original machine:

apt-clone clone `uname -n`

Then, on the machine to clone to, copy the clone file and run:

apt-clone restore original-machine-name.apt-clone.tar.gz

I include this answer here since this page turned up in initial web searches, but the other answer did not. This method looks way easier.