I just renamed my local branch using
git branch -m oldname newname
As mentioned, delete the old one on Github & re-push, though the commands used are a bit more verbose than necessary:
git push origin :name_of_the_old_branch_on_github git push origin new_name_of_the_branch_that_is_local
Simple. Dissecting the commands a bit, the git push command is essentially:
git push <remote> <local_branch>:<remote_branch>
So doing a push with no local_branch specified essentially means "take nothing from my local repository, and make it the remote branch". I've always thought this to be completely kludgy, but it's the way it's done.
Edit: As of Git 1.7 there is an alternate syntax for deleting a remote branch:
git push origin --delete name_of_the_remote_branch
Edit: As mentioned by @void.pointer in the comments
Note that you can combine the 2 push operations:
git push origin :old_branch new_branch. This will both delete the old branch and push the new one.