What exactly does the "u" do? "git push -u origin master" vs "git push origin master"

The key is "argument-less git-pull". When you do a git pull from a branch, without specifying a source remote or branch, git looks at the branch.<name>.merge setting to know where to pull from. git push -u sets this information for the branch you're pushing.

To see the difference, let's use a new empty branch:

$ git checkout -b test

First, we push without -u:

$ git push origin test
$ git pull
You asked me to pull without telling me which branch you
want to merge with, and 'branch.test.merge' in
your configuration file does not tell me, either. Please
specify which branch you want to use on the command line and
try again (e.g. 'git pull <repository> <refspec>').
See git-pull(1) for details.

If you often merge with the same branch, you may want to
use something like the following in your configuration file:

    [branch "test"]
    remote = <nickname>
    merge = <remote-ref>

    [remote "<nickname>"]
    url = <url>
    fetch = <refspec>

See git-config(1) for details.

Now if we add -u:

$ git push -u origin test
Branch test set up to track remote branch test from origin.
Everything up-to-date
$ git pull
Already up-to-date.

Note that tracking information has been set up so that git pull works as expected without specifying the remote or branch.

Update: Bonus tips:

• As Mark mentions in a comment, in addition to git pull this setting also affects default behavior of git push. If you get in the habit of using -u to capture the remote branch you intend to track, I recommend setting your push.default config value to upstream.
• git push -u <remote> HEAD will push the current branch to a branch of the same name on <remote> (and also set up tracking so you can do git push after that).

git push -u origin master

… is the same as:

git push origin master ; git branch --set-upstream master origin/master

Do the last statement, if you forget the -u!

Or you could force it:

git config branch.master.remote origin
git config branch.master.merge refs/heads/master

If you let the command do it for you, it will pick your mistakes like if you typed a non-existent branch or you didn't git remote add; though that might be what you want. :)

In more simple terms:

Technically, the -u flag adds a tracking reference to the upstream server you are pushing to.

What is important here is that this lets you do a git pull without supplying any more arguments. For example, once you do a git push -u origin master, you can later call git pull and git will know that you actually meant git pull origin master.

Otherwise, you'd have to type in the whole command.