Até onde eu sei, Rubygems no Ubuntu e Debian usam / var / lib / gems / $ ruby_version como sua raiz de instalação (para manter as gemas instaladas via apt e gems manualmente instaladas separadas).
No seu caso, como você está usando o Ruby 1.9, os executáveis devem ser instalados em /var/lib/gems/1.9/bin. Tente adicionar algo assim em seu arquivo ~ / .bashrc:
export PATH="/var/lib/gems/1.9/bin:$PATH"