How can I push a local Git branch to a remote with a different name easily?

When you do the initial push add the -u parameter:

git push -u origin my_branch:remote_branch

Subsequent pushes will go where you want.

EDIT:

As per the comment, that only sets up pull.

git branch --set-upstream

should do it.