I know this question is well answered, but just wanted to list the steps I take to create a new branch "myNewBranch" and push to remote ("origin" in my case) and set up tracking. Consider this the "TL;DR" version :)
# create new branch and checkout that branch
git checkout -b myNewBranch
# now push branch to remote
git push origin myNewBranch
# set up the new branch to track remote branch from origin
git branch --set-upstream-to=origin/myNewBranch myNewBranch