Descargar videos de Youtube en Linux Ubuntu es muy fácil. Con ver el video completo ya lo tendrán en su computadora, guardado en una carpeta temporal. Al cerrar el navegador, esta carpeta se limpiará. Para guardarlo definitivamente, antes de cerrar vayan a /tmp y copien el .flv a otro lugar.

Supongo que es igual para todas las distribuciones de Linux, pero en Ubuntu y Kubuntu puedo asegurarlo.