$ sudo add-apt-repository ppa:nilarimogard/webupd8
$ sudo apt-get update
$ sudo apt-get install youtube-dl
Atualização: Da mesma forma, em vez de usar qualquer PPA de terceiros, você pode usar o comando curl ou wget para instalar a versão mais recente do script youtube-dl, conforme mostrado.
$ sudo curl https://yt-dl.org/latest/youtube-dl -o /usr/local/bin/youtube-dl
OR
sudo wget https://yt-dl.org/downloads/latest/youtube-dl -O /usr/local/bin/youtube-dl
Depois de baixar o script, defina a permissão executável.
$ sudo chmod a+rx /usr/local/bin/youtube-dl