There are a few packages that apt-get doesn't seem to find on my linode machine that my local machine running Ubuntu 9.04 does.

After I ran
apt-get update &
apt-get upgrade

I ran
apt-get install ruby1.8-dev ruby1.8 rdoc1.8 irb1.8 libreadline-ruby1.8 libruby1.8 libopenssl-ruby

Then I am informed
"Package ri1.8 is not available, but is referred to by another package.
This may mean that the package is missing, has been obsoleted, or
is only available from another source"

Any idea why this might work on my home machine but not the linode one?

Look at your /etc/apt/sources.list on the two systems - any difference?

Aye, quite a few. I suppose that needs to be updated.