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.