App disappears from Permission Set included with package

Unfortunately, App and Tab visibility settings from packaged permission sets do not reflect in the destination org because Assigned Apps and tab visibility settings are not included in permission set components.

This is mentioned in the Packaging Guide. You can vote up for this Idea on IdeaExchange so that this may get considered for a future release.

App and Tab visibility can be managed in a permission set as of Spring '12; however, neither are currently supported in packaging (and only tab settings are supported in the metadata API). As a result, assigned apps as a setting cannot be packaged although they can be manually configured on the permission set post installation.

Just an FYI (in case you're not already aware), at the time of writing Permission Sets are only available in Enterprise, Unlimited, and Developer edition orgs.

Thus by using them you are making your package incompatible with Professional Edition. This may not be an issue in your use case but thought I'd flag it just in case.