Procure:
find / -name ruby 2> /dev/null
Se você obtiver um local positivo, verifique se o diretório está em $PATH . Se você não obtiver nenhuma saída, sua instalação do Ruby não foi planejada.
No Debian 6, eu desinstalei o Ruby 1.8 e instalei o 1.9.1. Agora, se eu executar which ruby , isso não produzirá nada. Por que não consegue mais encontrar rubi?