adb to program, który dystrybuowany jest wraz z Android SDK, dlaczego spodziewasz się, że będzie on w Twojej dystrybucji Linuksa? Musisz ściągnąć SDK i dodać ścieżkę do adb do swojego $PATH (najlepiej zrobić to w skrypcie startowym Twojego shella - np. w .bash_profile):
export PATH=$PATH:$HOME/android-sdk-linux_86/tools/
(zakładając, że wypakowałeś SDK w katalogu domowym)
albo utworzyć linka do adb gdzieś w standardowych ścieżkach, które już są dodane do $PATH (np. /usr/local/bin, żeby za badzo nie śmiecić sobie w systemie):
ln -s $HOME/android-sdk-linux_86/tools/adb /usr/local/bin/