Sous debian (et dérivés) un simple apt-get installer le nécessaire:
apt-get install youtube-dl suffira

Ensuite il vous suffira de lancer un terminal et d'y taper youtube-dl et l'adresse de la vidéo pour que celle-ci soit téléchargée, par exemple:
youtube-dl http://youtube.com/watch?v=OAKZwJAdtH4

Pour réencoder la vidéo dans un format plus "user friendly", utilisez la commande suivante:
ffmpeg2theora OAKZwJAdtH4.flv --optimize
Ou:
ffmpeg -i OAKZwJAdtH4.flv nom_de_fichier.avi

Ce qui créera, dans le répertoire correspondant, un .ogg (bien) ou un avi (moins bien :p) suivant ce que vous préférez.