Рассмотрите возможность установки libruby-extras. В описании говорится, что он содержит некоторые библиотеки, включая openssl.
EDIT: Дальнейшее исследование показывает, что libruby-extras зависит от libopenssl-ruby1.8, тогда как этот входит в libruby1.8 (по крайней мере, у maverick, но должен быть похож на более старый ubuntus) - так что вы, возможно, уже установили библиотеку, которую вы ищете, с libruby (если у вас есть libruby).