Despite having all libzlib dependencies installed, I would still get an error when trying to use gem install
As it turns out you need to do an additional step to solve this problem, using your ruby source.
cd <ruby_source>/ext/zlib
make
make install
Now gem install will work fine.