I had to jump through a few hoops..
I tried the obvious "sudo gem install activerecord", but it gave an error - it needs to install the i18n gem, but that needs rubygems version >= 1.3.6, and I had rubygems 1.3.5.
So I had to upgrade rubygems first, which would normally be :
sudo gem update --system
but that reports that it's been disabled on Debian, and directs you to use apt-get instead (which doesn't have a better version). So I had to use the gem-updater gem:
sudo gem install rubygems-update
sudo gem install activerecord
I still needed to get the mysql gem installed, which in turn needed the libmysql-dev stuff installed