How do I push a new local branch to a remote Git repository and track it too?

In Git 1.7.0 and later, you can checkout a new branch:

git checkout -b <branch>

Edit files, add and commit. Then push with the -u (short for --set-upstream) option:

git push -u origin <branch>

Git will set up the tracking information during the push.