So I can run on one machine:

dpkg --get-selections '*' > selection.txt

On another machine:

dpkg --set-selections < selection.txt

... followed by either of the following:

aptitude install

apt-get -u dselect-upgrade

... to install the packages that.

However, it appears that some information gets lost in the process, such as whether a package (say xyz) got installed automatically as dependency of another package (abc). You can see that whenever you do something like apt-get --purge remove abc. On the original machine you would be notified that package xyz was installed as dependency of abc and that you may use apt-get autoremove to get rid of it.

Now I am aware of deborphan and debfoster, but they're cumbersome to use given the (simple) task at hand.

It seems saving and restoring the selections as shown above is not sufficient to restore the subtle dependencies of installed packages.

Is there a way to back up the complete set of metadata for package management and restore it then in its entirety?