When working with github, refer to GHugo’s answer which gives a foolproof procedure with github. If you’re on an in-house (or other non-github) installation, read on.
You can always restore the previously observed state of master, by resetting to the old commit and issuing another push -f. The steps involved typically look like this:
# work on local master
git checkout master
# reset to the previous state of origin/master, as recorded by reflog
git reset --hard origin/master@{1}
# at this point verify that this is indeed the desired commit.
# (if necessary, use git reflog to find the right one, and
# git reset --hard to that one)
# finally, push the master branch (and only the master branch) to the server
git push -f origin master
Note, however, that this restores remote master to the state most recently retrieved by git fetch or equivalent. Any commits pushed by others after the last time you fetched will be lost. However, those commits will still be available in their reflogs, so they can restore them using steps like the above.