So I have been building and rebuilding my Linode 360 with Ubuntu 8.04. One thing I notice is the fact that I never seem to need to update any packages. I am pretty sure I have all of my sources setup correctly. So do the install images get updated on a regular basis?

You'll need to update them as you would with a physical server. You won't need to update your kernel packages though since they are not installed. The Linode Ubuntu image is pretty lean compared to the standard Ubuntu workstation install, so there is less to update.

If apt-get update && apt-get upgrade doesn't give you any updates, try running apt-get dist-upgrade. Some updates are only available through that option.

That said, it seems that default images here are kept pretty up-to-date, at least when it comes to Ubuntu 8.04 (don't know about other distros). For example, when I rebuilt my Linode a couple of weeks after the Debian OpenSSL bug was found, the default Ubuntu 8.04 image was already patched.

I created my linode based on Ubuntu 8.04 a few days ago, and when I finished the installation, there were a few updates. Do not remember what was updated, though. It seems fairly likely that Linode updates the images from time to time, and those few core packages does not face changes that often, so I would not be particularly concerned.

The simplest way to ensure your setup is working is to install some new package.

apt-get dist-upgrade is considered to be rather dangerous in ubuntu environment, for distribution upgrades "do-release-upgrade" should be used, while to resolve possible lockups between packages, "apt-get install packagename" does the trick.
Also, your situation is surely not related to this case, when there are packages not upgraded (which would be upgraded by dist-upgrade), apt-get upgrade shows them on the "not upgraded" list.