Based on the no longer existing post at: (now only accessible through Wayback Machine).

TL;DR Version

1. Prune Remote Branches

git remote prune origin

2. Delete locally linked branches to non-existent remote origins:

git branch -vv | grep 'origin/.*: gone]' | awk '{print $1}' | xargs git branch -D

This last command force the deletion of branches, so be sure you have pushed any local branch first.