Just for total clarity (if that's possible with Git :-) ), there are a couple of mostly-independent pieces here.
Every (local) branch can have one upstream. The upstream setting has several older names, but let's stick with "upstream" because it's the best name. :-) This upstream is what determines the parameter-free git push and git merge and git rebase. (I recommend avoiding git pull entirely at this point—all it does is run git fetch and then either git merge or git rebase, and it's better to manually control whether you do a merge or a rebase, until you're really familiar with Git so that you can recognize which one it did when things go wrong, as they always do eventually. Usually rebase is better anyway, and pull defaults to merging. You can reconfigure pull's default, but unless you're as obsessed with keystroke counting as the Git folks seem to be, I say: don't bother.)
There are many ways to set the upstream. (Note, by the way, that there's only one upstream—or, if you un-set it, no upstream. The point here, though, is that there are never two or more upstreams.) Once set, it gives you a bunch of conveniences. Besides the parameter-free commands, git status tells you more stuff, for instance.
The most direct way to set it is git branch --set-upstream-to.1 You can set the current branch's upstream:
git branch --set-upstream-to origin/zorg
or set some other branch's upstream:
git branch --set-upstream-to origin/zorg my-other-branch
(I'm using different local and remote-tracking branch names in this example, which is generally a bit unwise, but then again, why do you want to set your upstream to evilness? :-) ).
The thing is, the argument to --set-upstream-to—the remote-tracking branch name—has to be the name of an actual, existing remote-tracking branch that is there in your own repository right now. (Remember, a remote-tracking branch name is something in your repository. It's just called "remote-tracking" because your Git automatically updates it to what your Git sees on their Git, when you git fetch from the remote.)
When you create a new branch—one that doesn't exist on the remote yet—your own Git doesn't have a remote-tracking branch yet either. How could it? Your remote-tracking branches come from the remote, and they don't have it yet! So this means you can't use git branch --set-upstream-to, at least, not yet.
Once you do git push this new branch, your remote will have the branch, and your Git will add the corresponding remote-tracking branch. Then you'll be able to use git branch --set-upstream-to. But, quelle horreur, that requires typing in two commands! Hence, git push grew a --set-upstream aka -u option, so that you can tell your Git: "do this push, and then do the --set-upstream-to thing too." Because we all know that using two commands, like git fetchentergit rebase, is far too much to type when we could type git pull --rebase instead. Why, that saves three whole keystrokes!
(Slightly more seriously, the -u option to git push also works around complaints that can happen depending on how you have push.default configured. So it not only reduces keystrokes, it sometimes reduces confusion.)
Unless you need to change the upstream setting for some reason, you need only set it once. You can do that any time after the first push with git branch, or during the first push with -u, or any time after the first push with another push with -u. This just re-sets it.
1There is also git branch --set-upstream. One might think, given the Git programmers' obsession with fewer keystrokes, that this would be the command to use. But it has the wrong argument order: it got this shorter name by virtue of being put into git branch first. Then they found that people kept getting the arguments wrong, so they added the longer command-option.