libcurl3 - 7.18.2-1ubuntu4
libcurl3-gnutls - 7.18.2-1ubuntu4
libcurl4-openssl-dev - 7.18.2-1ubuntu4
via phwinfo.com
Google to the rescue!
I just had to run sudo apt-get install libcurl3 libcurl3-gnutls libcurl4-openssl-dev and my install of the fine Ruby library curl was just fine.