First you should install and use deborphan. This will find libraries and things that are no longer required.
Aptitude can find obsolete packages with aptitude search '~o'
My pre-aptitude command for doing this is below. But this shows some false positives when I just tested on a multiarch setup.
# the one-line command
diff -u <(dpkg --get-selections | awk ' {print "Package: " $1}' | sort -u) \
<(zcat /var/lib/apt/lists/*_Packages.gz | grep 'Package: ' | sort -u) \
| egrep '^\-'
# breaking it down down with some comments
# See all the installed packages
# dpkg --get-selections | awk ' {print "Package: " $1}' | sort -u
# see all the available packages
# zcat /var/lib/apt/lists/*_Packages.gz | grep 'Package: ' | sort -u
# compare and find the installed that are no longer available.
# diff -u <( installed ) <( available ) | egrep '^\-'