I ended up installing zlib from apt-get and then reinstalling ruby to not use the rvm directory for zlib.
Here’s how do:
$ sudo apt-get install zlib1g-dev
$ rvm reinstall 1.9.3
[Edit] As commenter @chrisfinne mentions, on CentOS/RedHat based systems:
$ sudo yum install zlib-devel
$ rvm reinstall 1.9.3