Hola,
Estuve viendo de donde bajar el programa, por lo visto la página del desarrollador no existe más:
http://www.marcosrodriguez.me/pytubeNo está en los repositorios de debian, y para Ubuntu pareciera que había que agregar un repositorio que tampoco existe más.
Yo lo bajé de:
http://pytube.softonic.com/linuxteniendo en cuenta que no es un sitio oficial, no es un repositorio oficial y la última actualización es del 2009.
Lo descomprimí y estando dentro del directorio lo ejecuto:
$ python pytube.py
o se puede copiar a /usr/share/pytube y copiar el ejecutable pytube.py a /usr/bin/
Yo lo ejecuté y estuve haciendo algunas pruebas pero no logré que bajara un video de youtube, puede se que me falte configurar algo, pero sí pude ejecutarlo, probalo de esa forma y contanos cómo te anduvo.
Saludos
Sofía