Hay un buscador de paquetes oficiales Debian en
http://packages.debian.org/
También tiene búsqueda de ficheros dentro de los paquetes, y si buscas
startx, verás que no pertenece a ningún paquete que se instale con GNOME, sino que pertenece al paquete
xbase-clients.
Si quieres instalar el "entorno gráfico",
apt-get install x-window-system.
Saludos.