No Debian, a maioria das bibliotecas é instalada em um caminho específico da arquitetura; assumindo que você está usando um PC típico de 64 bits (a arquitetura amd64 no Debian), você encontrará libQtCore.so e amigos em /usr/lib/x86_64-linux-gnu .
Para descobrir isso genericamente, você pode usar dpkg-architecture -qDEB_HOST_MULTIARCH (do pacote dpkg-dev ). Quando você estiver procurando por arquivos, confira apt-file : ele pode procurar por arquivos em todos os pacotes disponíveis no Debian, e apt-file search libQtCore encontra libqtcore4 e libqt4-dev em segundos.