This works in simple cases:
git rebase --preserve-merges master
Thanks to @Techlive Zheng in the comments.
You may see
fatal: refusing to merge unrelated histories
Error redoing merge a95986e...
Which means that git failed to automatically apply your subtree. This puts you in the situation @ericpeters described in his answer. Solution:
Re-add your subtree (use the same command you originally used):
git subtree add -P lib lib-origin master
Continue the rebase:
git rebase --continue
And you’re all set!
If you’re wondering if it worked successfully, you can compare with your original version after rebasing to make sure you didn’t change anything:
git diff <ref-before-rebase> <ref-after-rebase> -- .
(the -- . at the end instructs git to only diff the files in your current directory).
If all else fails and you don’t care about preserving the commits themselves, you can simply git cherry-pick the original subtree commit.
The commit message will look something like Add 'lib/' from commit '9767e6...' — that’s the one you want.