git におけるリモートリポジトリの操作は、「リモート上の何かを直接操作する」のではなくて「ローカルの変更をリモートに送りこむ」と考えれば理解しやすいのかもしれない。
リモートのタグを削除する
リモート origin のタグ TAGNAME を削除するには、次のようにする。
git push origin :tags/TAGNAME
リモートに「空のタグを送りこむ」という感じ。
リモートのブランチを削除する
リモート origin のブランチ BRANCHNAME を削除するには、次のようにする。
git push origin :BRANCHNAME
リモートに「空のブランチを送りこむ」という感じ。
追記（2012-09-13）
TAGNAME や BRANCHNAME の前にコロンを付けるかわりに、次のようにすることができるようです。こちらのほうが分かりやすいですね。
git push --delete origin tag TAGNAME
git push --delete origin BRANCHNAME