Não sei por que isso não foi colocado como uma resposta, vou apenas colocar aqui, com um excelente comentário de Charles Green.
android-tools-adb e android-tools-fastboot estão no repositório universe .
Você pode habilitá-lo em Centro de Software ou apenas clicar neste one-liner que habilitará e instalará tudo.
sudo add-apt-repository universe && sudo apt-get update && sudo install android-tools-adb android-tools-fastboot