From apt-get manual:

upgrade
   upgrade is used to install the newest versions of all packages
   currently installed on the system from the sources enumerated in
   /etc/apt/sources.list. Packages currently installed with new
   versions available are retrieved and upgraded; under no
   circumstances are currently installed packages removed, or packages
   not already installed retrieved and installed. New versions of
   currently installed packages that cannot be upgraded without
   changing the install status of another package will be left at
   their current version. An update must be performed first so that
   apt-get knows that new versions of packages are available.

dist-upgrade
   dist-upgrade in addition to performing the function of upgrade,
   also intelligently handles changing dependencies with new versions
   of packages; apt-get has a "smart" conflict resolution system, and
   it will attempt to upgrade the most important packages at the
   expense of less important ones if necessary. So, dist-upgrade
   command may remove some packages. The /etc/apt/sources.list file
   contains a list of locations from which to retrieve desired package
   files. See also apt_preferences(5) for a mechanism for overriding
   the general settings for individual packages.

And with the newer apt tool available from 14.04 onwards:

full-upgrade
   full-upgrade performs the function of upgrade but may also remove
   installed packages if that is required in order to resolve a
   package conflict.

In your particular case, I see, for example, that linux-headers is a virtual package that is provided by both linux-headers-3.0.0-12 and linux-headers-3.0.0-13 and that sounds like the kind of package installation and removal handled by dist-upgrade, but not by upgrade.

Yes, there are such files. In particular, *.list, *.postrm , and *.conffiles, which are all stored in /var/lib/dpkg/info directory.

The .postrm files are post-remove scripts, that run after a package is removed. Those scripts are responsibility of the package maintainers, and each script is tailored to the specific package. If you examine /var/lib/dpkg/info/usb-modeswitch-data.postrm for example , you will see something like this:

#!/bin/sh
set -e
# Automatically added by dh_installdeb
dpkg-maintscript-helper rm_conffile "/etc/usb_modeswitch.d/230d:0001" 20101222-3 -- "$@"
# End automatically added section

There's also *.list and *.conffiles files, which are basically lists. gnome-terminal.list, for example, will list all files and directories created when gnome-terminal was installed. The *.list files are very useful for determining what installed what. *.conffiles list all the config files for a package. For instance, while xterm.list gives all the files , `xterm.conffiles* gives only conffiles. In other words, the contents of conffile will also be present in list file.

$ cat /var/lib/dpkg/info/xterm.conffiles                                       
/etc/X11/app-defaults/XTerm
/etc/X11/app-defaults/KOI8RXTerm-color
/etc/X11/app-defaults/XTerm-color
/etc/X11/app-defaults/UXTerm-color
/etc/X11/app-defaults/UXTerm
/etc/X11/app-defaults/KOI8RXTerm

I don't quite know how *.conffiles work. My assumption is that the post-removal scripts take priority, and apt-get just uses those *.conffiles to double check that files listed there were removed.

As @A.B. properly reminded me, there are also *.prerm files, some of which do remove the .conf files, but not necessarily, for instance the one for xpdf app was removing the files in /etc/xpdf/includes directory