apt-cache search procura no banco de dados de pacotes local de repositórios ativados, em arquivos relevantes dentro do diretório /var/lib/apt/lists/ , pois presumivelmente o pacote não está disponível em nenhum de seus repositórios ativados, você não está recebendo nada esperado.
Existem diferentes técnicas para instalar pacotes a partir de qualquer arquivo arquivado (compactado) do usuário como o que você possui ( PCL_TLKBGL.tar.gz ) (normalmente) para extrair, criar, copiar ciclo. As instruções de instalação e desinstalação devem ser escritas dentro de algum arquivo dentro do arquivo, possivelmente em README .
Agora, como você usou um script install.sh para instalar o pacote, pode haver um uninstall.sh ou algum método mencionado, nunca se sabe. Então, extraia o arquivo compactado ( PCL_TLKBGL.tar.gz ) que você tem e verifique dentro de qualquer dica.
Como observação, se você usar sudo make install como o último estágio da instalação (isso copiará os arquivos relevantes para os diretórios mencionados), você deve olhar para checkinstall para criar um arquivo .deb dos arquivos e facilmente manter / remover usando gerenciadores de pacotes.