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 update_rubygems
after which I had rubygems 1.3.7. Then I could get active record:
sudo gem install activerecord

I still needed to get the mysql gem installed, which in turn needed the libmysql-dev stuff installed

sudo apt-get install libmysqlclient15-dev
sudo gem install mysql