Assumindo Jessie, como a resposta anterior ...
Em Jessie, o pacote bluez-utils foi removido. O Bluez 5 inclui ou tem todas as funcionalidades dele, não tenho certeza de qual.
Usar o aptitude (apt-get) como a resposta anterior lhe dará uma versão muito antiga (Bluez 5.23 atualmente), mas é a maneira mais fácil. Se você quiser a versão mais recente, por favor encontre-a no link e instale o tarball. ou seja:
wget http://www.kernel.org/pub/linux/bluetooth/bluez-5.49.tar.xz
tar xvf bluez-5.49.tar.xz
cd bluez-5.49
./configure
make
sudo make install
sudo reboot
Instalar o Bluez parece ser muito complicado, e eu sugiro o tutorial mais detalhado em link se você decidir seguir esse caminho.