Chris,
Published maps with relationship classes can be packaged with the copy setting. If the Intersect or Include All setting is used, the relationship class will not be packaged.
Joins and relates will not work with packaged pmf's, that's just the way it is unfortunately.
The difference with the relationship class is that you can identify a feature and get access to the related information, but it's not stored directly in the attribute table like the information from a join is.
If you're looking to permanently append the joined information, there isn't really any automated process for a workflow like that.
You can export the feature class that has a join from the Table of Contents (right-click > Data > Export Data). The output feature class will have the joined data permanently appended. When new data comes in (that is stored in the joined table) you would have to delete the fields with the joined info, rejoin, export. You could create a model that does this for you (deletes fields, joins data, exports), but other than that you're pretty stuck.
Unless, of course, your underlying data never changes (just the joined data) which would allow you to join a new table to an older version of the feature class and export.
I might focus on trying to store relative path names in the mxd and then providing data + pmf to the laptop.