Posts abound regarding this topic, and to help others save hours of trying different solutions, here is the final result of my hours of tinkering.
The three solutions around the internet at the moment are:
rubysspi
apserver
cntlm
rubysspi only works from a Windows machine, AFAIK, as it relies on the Win32Api library. So if you are on a Windows box trying to run through a proxy, this is the solution for you. If you are on a Linux distro, you're out of luck.
apserver seems to be a dead project. The link listed in the posts I've seen lead to 404 page on sourceforge. I search for "apserver" on sourceforge returns nothing.
The sourceforge link for cntlm that I've seen redirects to http://cntlm.awk.cz/, but that times out. A search on sourceforge turns up this link, which does work: http://sourceforge.net/projects/cntlm/
After downloading and configuring cntlm I have managed to install a gem through the proxy, so this seems to be the best solution for Linux distros.