Las últimas distros basadas en Debian no incluyen Celestia en sus repositorios y para volver a disfrutarlo hay que compilarlo.
Para ello solo tienes que teclear los siguientes comandos desde consola (en Ubuntu y distros derivadas):
sudo apt-get install libglew-dev libjpeg-dev libpng-dev libtheora-dev libgl1-mesa-dev libeigen3-dev libfmt-dev qtbase5-dev qtbase5-dev-tools libepoxy-dev libluajit-5.1-dev libqt5opengl5-dev freeglut3-dev libgtkglext1-dev liblua5.2-dev cmake build-essential checkinstall git
git clone https://github.com/CelestiaProject/Celestia
cd Celestia/
git submodule update --init
mkdir build
cd build/
cmake .. -DENABLE_QT=ON
make
sudo make install
Si usas Debian puro ejecuta el comando su - antes de introducir las instrucciones que empiezan con sudo, que deberás introducir sin la palabra sudo.
Lo puedes ejecutar con el siguiente comando:
celestia-qt
Recuerda que puedes crear un acceso directo para facilitar la ejecución del programa.
ACTUALIZACIÓN 26-08-2020: Soporte para Ubuntu 20.04 y Debian 10.

