To export a list of all installed packages, you can use the following command:

sudo dpkg --get-selections > selections.txt

But this will loose any {A} markers for automatically installed packages and therefore produce a lot of garbage when dependencies change.

To export only manually installed packages, use aptitude like this:

sudo aptitude search '~i!~M' -F '%p install' > selections.txt

(More aptitude filterstrings can be found on their project page.)

On the other machine, use the following command to set the new markers:

sudo dpkg --set-selections < selections.txt

Now run aptitude and resolve the dependencies.