How do you get Ubuntu to automatically run a program every time the screen is unlocked?

It is possible, albeit a bit tricky. GnomeScreensaver documentation states:

Is there a way to perform actions when the screensaver activates or deactivates? Or when the session becomes idle?

One way is to watch for the D-Bus signals from gnome-screensaver. Here's an example of how to perform actions when the session becomes idle or is no longer idle using the Perl language:

my $cmd = "dbus-monitor --session \"type='signal',interface='org.gnome.ScreenSaver',member='SessionIdleChanged'\"";

open (IN, "$cmd |");

while (<IN>) {
    if (m/^\s+boolean true/) {
        print "*** Session is idle ***\n";
    } elsif (m/^\s+boolean false/) {
        print "*** Session is no longer idle ***\n";
    }
}

Although when I examined using dbus-monitor and proceeded to lock/unlock the screen the signal emitted was

path=/org/gnome/ScreenSaver; interface=org.gnome.ScreenSaver; member=ActiveChanged
boolean true

when screen was locked and

path=/org/gnome/ScreenSaver; interface=org.gnome.ScreenSaver; member=ActiveChanged
boolean false

When unlocked.

So altering the above script,

my $cmd = "dbus-monitor --session \"type='signal',interface='org.gnome.ScreenSaver',member='ActiveChanged'\"";

open (IN, "$cmd |");

while (<IN>) {
    if (m/^\s+boolean false/) {
        exec('/path/to/your/script');
    } 
}

should do it.

Building on the bash shell script Michael wrote:

#!/usr/bin/env bash
dbus-monitor --session "type='signal',interface='org.gnome.ScreenSaver',member='ActiveChanged'" | while read line ; do 
    if [ x"$(echo "$line" | grep 'boolean true')" != x ] ; then 
        # runs once when screensaver comes on...
    fi
    if [ x"$(echo "$line" | grep 'boolean false')" != x ] ; then 
        # runs once when screensaver goes off...
    fi
done

Doing it in bash to share the same external script:

#!/usr/bin/env bash
dbus-monitor --session "type='signal',interface='org.gnome.ScreenSaver',member='ActiveChanged'" | while read line ; do 
        if [ x"$(echo "$line" | grep 'boolean false')" != x ] ; then 
               # do whatever you want here
        fi
done