Once restored, site and app store came up just fine - except - oddly, any non-out of the box apps that were deployed no longer worked. Clicking on them immediately triggered a 404. A check in Fiddler verified that the URL's were indeed right.
Having walked in on the situation, we started looking for a cause. Oddly, dropping and re-adding the apps worked just fine. Started checking the apps out in the site and found that indeed all of the apps were there an registered. The only error generated (in the System Event Log) was "app principal was not found" indicating that the app wasn't registered. Checking everything, all GUID's were good and they did appear registered so what gives?
Minor detail: All of the app information (licenses, registration, etc.) is actually in the App Management Service database. When bringing over the content DB's, it is also necessary to bring this since the registrations are needed for the sites.
So - the simple answer is to be sure to restore Service Application databases when necessary, specifically the App Management Service and the Secure Store if there are connection apps defined there.
However, this is not without issues - if you are restoring only a single app, site collection, etc. and you have others that already exist, overlaying the AMS DB will break all existing sites. It would appear that there is only the manual fix of dropping and adding apps back to the given site. I have not found another workaround (if you know one, please comment!).