How does Ubuntu keep track of the "System restart required" flag in motd?

Solution 1:

Check for the presence of /var/run/reboot-required.

Solution 2:

The script that generates the reboot required part of motd is /usr/lib/update-notifier/update-motd-reboot-required which contains:

#!/bin/sh -e
#
# helper for update-motd

if [ -f /var/run/reboot-required ]; then
        cat /var/run/reboot-required
fi

Your nagios check could check for the existence of /var/run/reboot-required.

Solution 3:

Additionally the file '/var/run/reboot-required.pkgs' lists the packages that requested the reboot. For example:

$ cat /var/run/reboot-required.pkgs 
linux-image-2.6.32-28-generic
dbus
$

On Ubuntu Lucid (10.4).