Obsolete packages vs. orphaned packages

For short, obsolete packages are not in any repository on your list anymore. Orphaned packages are automatic dependencies whose "dependants" have all been uninstalled. And apt-get autoremove only considers orphaned packages that were installed by apt to resolve dependencies.

Obsolete packages

As you probably know, apt keeps a list of repositories it can fetch packages from. But sometimes, packages are removed from a repository. Maybe nobody takes care of (maintains) the package any more, and the (very) old last version available has become a security risk. Or maybe the program has changed its name, the package names were changed accordingly and the old packages under the old name are removed. There are other possible reasons why a package is removed from a repository, as well.

If a package is installed on your system, but can no longer be found in any of the repositories your apt has on its lists, that package is considered "obsolete".

Orphaned packages

As you probably know as well, apt can manage dependencies between packages. Say for example, a program called "greatprogram" needs a library called "greatlibrary" to work. So, the package containing greatlibrary can be marked as a automatic dependency of the package containing greatprogram. You won't be able to install the greatprogram package, unless greatlibrary is already installed (or will be installed with the same command).

But what if you uninstall greatprogram on a later day and leave greatlibrary behind? In that case, once at least one other package needed greatlibrary as a dependency, but now no other package does any longer. Those "left behind" packages are called "orphaned packages".

apt-get autoremove

Still another fact you probably know, is that apt can resolve dependencies automatically for you. Say you want to install the before mentioned greatprogram, but don't have greatlibrary installed yet. apt-get "notices" that there is an unsatisfied dependency and offers you to install greatlibrary as well.

apt-get autoremove offers you to remove any orphaned packages that have been installed this way to resolve a dependency. Orphaned packages that have been installed in other ways are not in autoremove's list. If, say, you installed greatlibrary yourself before installing greatprogram, and on a later day uninstall greatprogram, greatlibrary would still be orphaned. But autoremove would not take care of it, because it has not been installed automatically as a result of an resolved dependency.