Ok, acho que tenho que postar alguma coisa, já que estou dizendo às pessoas que elas estão incorretas.
No caso do sqlite-ruby, o libsqlite3-dev deve fazê-lo.
Para ficar claro, o pseudo-pacote ruby-full apenas instala todos os "componentes" para uma instalação de quase todos os tipos de ruby. Não faz absolutamente nada pela satisfação da dependência de gemas que contêm componentes binários.
Para descobrir quais pacotes dev requerem uma gem você pode ocasionalmente checar o specfile da gem ou a página em rubyforge. Se ele reclamar que um arquivo específico não foi encontrado, um pouco de pesquisa criativa (a palavra fornece ajuda com frequência) deve ajudá-lo a localizar o pacote -dev necessário.
Outro site útil para esse tipo de coisa é a pesquisa de pacotes do ubuntu: link
Outro ponto digno de nota é que o Ubuntu está tomando o Debian neste e tentando pré-construir pacotes intitulados ruby-gemname ou similar no aptitude para simplificar o gerenciamento de pacotes e rastrear mudanças de gem. Isso quebra algumas das exigências em alguns scripts ruby. Eu tenho muito o discurso sobre esse assunto, mas eu discordo.
Se você instalar o libsqlite3-dev e ele ainda não funcionar - certifique-se de estar usando a gem de arquitetura correta (isso não é necessariamente automático, talvez um recurso futuro seja ótimo para os desenvolvedores).
Se você tiver essa biblioteca instalada e tiver certeza de que a arquitetura da gem está correta, poste em qual arquivo ela está pendurada e veremos o que posso descobrir.