Who provides implementation(s) of the PackageManager class?

The real implementation for the PackageManager is PackageManagerService located at frameworks/base/services/java/com/android/server/

You can find the source code here in the GrepCode.

PackageManager is abstract and a concrete implementation needs to be provided in order to invoke instance methods. An implementation of this class can be found as a package private static class of ApplicationContext which itself is available in ContextImpl. (For source code see here). Note that this implementation of PackageManager is final and so cannot be overriden.

There is also a MockPackageManager implementation that might interest you.

It is ApplicationPackageManager, and it is created in ContextImpl.getPackageManager().