For the TL;DR version, see VonC's answer.
git remote add adds a remote. Remotes can have any name you like, though by convention, origin is the first one, and upstream is often the second. But normally if you added a second remote it would have a different URL, not the same URL. You only need more than one remote if you talk to multiple different Git repositories, each at different URLs.
Confusingly, the remote named upstream (assuming you have one) is not an upstream, it's just a remote.
The term upstream, when applied to a branch name, refers to what is internally a two-part setting (as VonC said). Every branch name, such as master or feature, can have one upstream, or no upstream. Typically the upstream of master would be origin/master and the upstream of feature would be origin/feature. If you did have multiple remotes, and called the second one upstream, you could set the upstream of branchX to upstream/branchX.
So: the upstream of a branch is some other name, typically one starting with the name of a remote. Git uses this setting to remember "that's where I fetch/pull from" and "that's where I push to". This name must actually exist, though, and that's where things really get confusing.
So I created a new branch taken from the master
git checkout -b sample-branch master
Switched to a new branch 'sample-branch'
Technically, this creates a new branch name in your own Git repository, named sample-branch. The commit hash ID selected by this new branch name is the same as the commit hash ID selected by the existing name master (also a branch name).
When you use this kind of git checkout command, your Git will set the upstream of the new branch to the name of the other branch if it is, say, origin/sample-branch. But you probably don't have an origin/sample-branch. This name would only exist if the Git over at origin—at the URL stored in the remote named origin, that is—has a branch named sample-branch, and your Git had seen this and copied it over. Since you didn't use origin/sample-branch here—and if you did, it would just fail anyway—your Git didn't set an upstream for the new branch.
You need to do something eventually about this. There's no need to do this right away! You can do it whenever you like. But eventually, you do need to do it. There are two steps involved:
You must get the other Git, the one over on origin, to create a branch named sample-branch. When you get that Git to create its sample-branch, your Git can now copy that to your origin/sample-branch, so that your origin/sample-branch exists.
Once your origin/sample-branch exists, you need to get your Git to set origin/sample-branch as the upstream for sample-branch.
You can do this two step process with two separate Git commands, and in the ancient past, you had to do it that way. With modern Git versions, though, one command suffices. That one command is git push -u origin sample-branch.
What this does is:
Have your Git call up their Git (the Git at origin) using the URL stored in the name origin.
Your Git offers their Git any new commits and other objects required to complete the overall task. Your Git will then send commits and their contained files if needed. Once they have everything required, your Git then sends them a polite request: Please, if it's OK, create or update your name sample-branch so that it identifies a particular commit. The particular commit your Git recommends here is the same commit that your name sample-branch identifies.
If they accept this request, that creates their sample-branch. Since your Git now sees that their Git has sample-branch, your Git creates your origin/sample-branch to remember this.
Now that your Git has origin/sample-branch, your git push -u automatically invokes git branch --set-upstream-to=origin/sample-branch sample-branch.
If you wish, for some reason, to do this the old two-step way, run:
git push origin sample-branch:sample-branch
(the two names here separated by the colon tell your Git what to tell their Git). Then, when that has succeeded, run:
git branch --set-upstream-to=origin/sample-branch sample-branch
Obviously the single git push -u command is shorter and easier.
