git branch --set-upstream local origin/remote
local and remote are the names of your local resp. remote branches.
In Git version 1.8 and later, it’s even easier. Make sure you’re on the local branch, and then:
git branch --set-upstream-to origin/remote