Okay, so I think I have to post something since I'm telling folks they are incorrect.
In the case of sqlite-ruby libsqlite3-dev should do it.
To be clear the ruby-full pseudo package only installs all of the "components" for an almost all option ruby installation. It does absolutely nothing for dependency satisfaction for gems containing binary components.
To find out what dev packages a gem requires you can occasionally check the gem's specfile or the page on rubyforge. If it complains about a specific file not being found a little creative googling (the word provides often helps) should help you locate the -dev package that is required.
Another useful site for this type of thing is ubuntu package search: http://packages.ubuntu.com/search?mode=exactfilename&suite=intrepid§ion=all&arch=any&searchon=contents&keywords=sqlite.h
Another point worth noting is that Ubuntu is siding with Debian on this one and trying to prebuild packages titled ruby-gemname or similar into aptitude to simplify package management and track gem changes. This does break some of the requires in some ruby scripts. I have quite the rant on that topic, but I digress.
If you install libsqlite3-dev and it still doesn't work - ensure you are using the correct architecture gem (this is not necessarily automatic, maybe a future feature would be great gem developers).
If you have that library installed and you are sure the architecture on the gem is correct, post what file it hangs on, and I'll see what I can dig up.