Se você seguiu o tutorial da nvidia, provavelmente instalou os drivers proprietários. Eu não tive muita sorte com isso, então aqui está uma solução usando os drivers modificados. Certifique-se de remover qualquer driver nvidia ou instalação do cuda antes de seguir estas instruções.
Instale os drivers:
sudo add-apt-repository ppa:xorg-edgers/ppa
sudo apt-get update
sudo apt-get install nvidia-XXX nvidia-prime
Reinicie o computador e verifique se os drivers estão instalados corretamente. Para verificar, instale as configurações do nvidia x server. Se a sua GPU for encontrada, este software exibirá informações sobre sua placa gráfica.
Em seguida, instale o kit de ferramentas cuda do repositório padrão:
sudo apt-get install nvdia-cuda-toolkit
Em seguida, instale a biblioteca cuda correta do repositório adicionado anteriormente:
sudo apt-get install libcuda1-XXX
sudo add-apt-repository -r ppa:xorg-edgers/ppa
XXX nos itens acima dependerá de qual placa gráfica você tem (maior XXX significa um driver mais recente). Para mim (eu tenho uma nvidia 970M) foi 346 (EDIT: este foi o mais recente driver na época, agora é 361. A maioria das placas de vídeo será compatível com o driver mais recente, mas verifique o site da nvidia para ser seguro).
Finalmente, tente executar o deviceQuery (pode ter que ser executado como sudo) para ver se o cuda está instalado e localizando seu gpu.