Para pacotes curtos e obsoletos, eles não estão mais em nenhum repositório da sua lista. Pacotes órfãos são dependências automáticas cujos "dependentes" foram todos desinstalados. E apt-get autoremove considera apenas pacotes órfãos que foram instalados por apt para resolver dependências.
Pacotes obsoletos
Como você provavelmente sabe, apt mantém uma lista de repositórios dos quais ele pode buscar pacotes. Mas às vezes, os pacotes são removidos de um repositório. Talvez ninguém mais cuide de (mantém) o pacote, e a última versão (muito) antiga disponível se tornou um risco de segurança. Ou talvez o programa tenha mudado seu nome, os nomes dos pacotes foram alterados de acordo e os pacotes antigos com o nome antigo foram removidos. Existem outras razões possíveis pelas quais um pacote é removido de um repositório também.
Se um pacote estiver instalado em seu sistema, mas não puder mais ser encontrado em nenhum dos repositórios que seu apt tiver em suas listas, esse pacote será considerado "obsoleto".
Pacotes órfãos
Como você provavelmente já sabe, apt pode gerenciar dependências entre pacotes. Digamos, por exemplo, que um programa chamado "greatprogram" precisa de uma biblioteca chamada "greatlibrary" para funcionar. Assim, o pacote contendo greatlibrary pode ser marcado como uma dependência automática do pacote contendo greatprogram. Você não poderá instalar o pacote greatprogram, a menos que o greatlibrary já esteja instalado (ou será instalado com o mesmo comando).
Mas e se você desinstalar o programa great em um dia posterior e deixar a greatlibrary para trás? Nesse caso, uma vez que pelo menos um outro pacote necessitasse de uma grande biblioteca como dependência, agora nenhum outro pacote faz mais tempo. Esses pacotes "para trás" são chamados de "pacotes órfãos".
apt-get autoremove
Ainda outro fato que você provavelmente sabe, é que apt pode resolver dependências automaticamente para você. Digamos que você queira instalar o greatprogram mencionado anteriormente, mas ainda não tenha a greatlibrary instalada. apt-get "percebe" que existe uma dependência insatisfeita e oferece a você também a instalação de greatlibrary.
apt-get autoremove oferece-lhe para remover quaisquer pacotes órfãos que foram instalados desta forma para resolver uma dependência . Pacotes órfãos que foram instalados de outras maneiras não estão na lista de autoremove. Se, digamos, você instalasse a greatlibrary antes de instalar o greatprogram e, em um dia posterior, desinstalasse o greatpribrary, a greatlibrary continuaria órfã. Mas autoremove não cuidaria disso, porque não foi instalado automaticamente como resultado de uma dependência resolvida.