How can I tell what package requires a reboot of my system?

Short version:

cat /var/run/reboot-required.pkgs

Explanation:

Looks like there is an easy way to automatically extract the requested information.

Inside .deb files there are control files for installation, including postinst (run after installation).

For example, in linux-image-2.6.35-25-generic_2.6.35-25.44_amd64.deb,
postinst includes

my $notifier          = "/usr/share/update-notifier/notify-reboot-required";

my $warn_reboot     = 'Yes';     # Warn that we are installing a version of
                                 # the kernel we are running

and

# Warn of a reboot
if (-x $notifier) {
 system($notifier);
}

---

The shell script /usr/share/update-notifier/notify-reboot-required updates
/var/run/reboot-required and /var/run/reboot-required.pkgs.

The latter file contains a list of packages requesting a reboot.

Reboot is recommended by the unattended-upgrades when it sees that a /var/run/reboot-required exists. The file is created by postinst (post-installation) scripts in some packages, it looks something like this:

[ -x /usr/share/update-notifier/notify-reboot-required ] && \
/usr/share/update-notifier/notify-reboot-required || true

If you want to see which packages triggered this, you can have a look at the contents of the /var/run/reboot-required.pkgs file.

For more info also see this thread.

Based on Olli's earlier answer, I came up with a method to find all currently installed packages on your system that requires a reboot.

~$ mkdir debs
~$ cd debs
~/debs$ apt-get download $(dpkg -l | tail -n +7 | awk '{print $2}')

Wait for the download to complete, on my system it was around 900 MB so it might take a while depending on your connection. Then:

~/debs$ for x in $(ls); do y=$(dpkg-deb -I "$x" postinst 2>/dev/null | grep 'reboot-required'); if [ -n "$y" ]; then echo "$x" | grep -Poe '^.*?(?=_)'; fi; done

The output may look something like this:

dbus
gconf2
initscripts
libc6
libpam0g
libpam-systemd
libssl1.0.0
linux-image-3.19.0-47-generic
linux-image-3.19.0-49-generic
network-manager
upstart

Of course, this method is not foolproof. There might be packages that notifies about the required reboot through other means than 'notify-reboot-required', and while this shows which currently installed packages require or doesn't require a reboot, it is not certain the same will hold true for later versions of the same package.