I don't know if there is a better way (there probably is), but depending on the scale you need, you could use aptitude's search feature for part of the machinery. It lets you search for packages matching a pattern. So, aptitude search '~i'
gives you all installed packages
We need to go a step further, though. The packages manager likes to know which packages were directly requested by you and which ones were just pulled in because of other packages. Without that information, ugly stuff can happen. So, we can expand on that search pattern to select packages that are not automatically installed: aptitude search '!~M ~i'
The search feature is covered in some detail in Aptitude's reference manual.
Now, you have your list of packages to install. You can format the output as necessary by passing the -F flag to that command, like -F '%p' to get a list with just package names.
For example, you could run this on machine 1:
aptitude -F "%c %p" --disable-columns search '!~M ~i' | awk -F " " '{ print "apt-get -y install " $2 }' > aptshell.sh
Then copy the newly created aptshell.sh
file over to machine 2 and and use this command on machine 2 to run it there:
sudo sh aptshell.sh
Then repeat the process, with the original machine 2 as the new machine 1, and the original machine 1 as the new machine 2. Now each machine has all the packages that were formerly only on the other.