How to Fix 'Updates Were Rejected' (Without Force-Pushing and Losing Someone's Work)

Adapted from the Git & GitHub Companion Guide. You finish up some work, run git push, and instead of the usual quiet success, you get this: $ git push To github.com:you/project.git ! [rejected]