There are apps (such as https://play.google.com/store/apps/details?id=com.teslacoilsw.launcher) that are free, but whose paid features can be enabled by buying another app (in this case, this one https://play.google.com/store/apps/details?id=com.teslacoilsw.launcher.prime)
How does this work?
My guess is that the free apps launches an explicit Intent and can detect if the app is present via a try/catch structure. The downside of this is that this could be easily circunvented by someone who creates an app with the same package name and specifies all possible Intent filters.
Is this how it works, or is it some other way?
The easiest way is to use startActivityForResult(...) from app A against an Activity of app B, that must be configured with an IntentFilter in order to be used from an outer app. Inside the B called activity you can also check who's calling with getCallingActivity(). You can find an example here.
Before starting the Activity, you can test that B is installed (using the PackageManager) or you can just start the activity and catch the Exception.
In the called Activity, you can check the signature of the calling package using the PackageManager.checkSignature(String,String) method. Pass the package name of A and B and if the signature matches, execute the logic.