Esta é sua resposta:
http://kristofhouwen.wordpress.com/2009/02/01/install-sqlite3-ruby-gem-on-ubuntu-810/
Primeiro eu instalei o banco de dados Sqlite3:
sudo apt-get install sqlite3
Depois disso, instalamos o lib para não recebermos o erro:
sudo apt-get install libsqlite3-dev
Agora podemos instalar a gema sem o erro:
sudo gem install sqlite3-ruby
O primeiro comando (instalando o sqlite3) pode não ser necessário.