先にまとめを書いておく。
@haltさんに教えてもらった、より正しいやり方をまとめておく)

まとめ

リモート上のブランチを消す方法

$ git push origin :hogehoge

ローカルにあるリモート情報のブランチを消す方法

$ git branch -rd origin/hogehoge

リモート上の削除されたブランチがあるかどうか確認する方法

$ git remote show origin

リモート上の削除されたブランチをローカルから消す場合

その1

$ git remote prune origin

その2

$ git pull --prune

ぐだぐだ説明

Gitでリモート上にあるブランチを消す場合、

$ git push origin :hogehoge

みたいにやれば消せるんだけど、削除した端末とは別の端末で、

$ git branch -a

とかやると出てきたりする。

$ git fetch origin

とかやっても、依然として一覧には残ったまま表示される。

これは、git-fetch

ローカルにないやつを取りに行く

という機能だかららしいんだよね。
なんか勝手に情報を最新にしてくれるもんだと思っていたけど、違うくさい。
つまり同期をとってくれるわけではない!

んで、リモートに無いブランチがローカルに見えているのも気持ち悪いので、手動で消してあげる。

$ git branch -rd origin/hogehoge

これでOK。

@haltさんに教えてもらいpruneを使って消す方法

$ git pull --prune

「pullしようと思ったけど、ねえよばか」とエラーを吐きつつ消してくれています。 後は

$ git remote show origin

ってやると

Remote branches:
master tracked
refs/remotes/origin/hogehoge stale (use 'git remote prune' to remove)

stale(新鮮じゃない)よって出るので、こいつを指示通り

$ git remote prune origin

とかやるとOK。
けど、やる前に

$ git remote prune -n origin

ってやると、dry-runで実行してくれるので安心。

深いっす。
ネット上にpruneってあんまり無かったんで、存在しらなかったです。