Para procurar por pacotes na linha de comando, você pode usar:
apt-cache search -n pattern
para pesquisar apenas nomes de pacotes ou omitir a opção -n para pesquisar as descrições também. Isso irá procurar todos os arquivos que você listou em seu diretório /etc/apt/sources.list e /etc/apt/sources.list.d/, assumindo:
sudo apt-get update
foi executado primeiro. Isso inclui repositórios padrão do Ubuntu, como main, universe, multiverse e qualquer repositório externo ou PPA listado. Ele também suporta padrões de regex POSIX (veja o regex (7) manpage), assim você pode fazer coisas interessantes como:
apt-cache search -n '^python-.{3}$'
para procurar apenas pacotes que tenham o formato python-ABC para qualquer caractere ABC.
Para verificar o status instalado a partir da linha de comando, bem como de qual repositório o pacote é originado, você pode usar:
apt-cache policy package-name