Here's the "TL;DR" version (which glosses over a lot of special cases): git fetch always updates FETCH_HEAD, with more than one line in various cases.  It sometimes updates "remote branches", which are refs whose full name starts with refs/remotes/.  The rest is mostly about the "sometimes", which vary based on both the number of arguments given to git fetch, and the git version.
I had a chance to test this.  Let's distinguish three cases, all of which assumes running git fetch without extra options like -a or even --all.  Let's also exclude the weirder variants of git fetch, like using a URL directly, or the insteadOf entries, or files listed in .git/remotes or .git/branches.  (I admit I'm just guessing, but I think these are left-overs from the days before the [remote "name"] entries went into git's config files.  Edit, 2019: that turns out to be correct.)
- git fetch, and no other arguments.
 - Git determines your current branch (in the usual way, by reading - HEAD, but you can of course see what it is with- git branchor- git status).  It then looks for a config entry for that branch naming its- remote.  For instance, suppose you're on branch- dummyand- .git/confighas (among other entries):
 - [branch "dummy"]
    remote = remote-X
 - In this case - git fetchis equivalent to- git fetch remote-X.  After that point, this is equivalent to case 2, which is:
 
- git fetch remote(and no more arguments beyond that).
 - Git does not look at your current branch this time.  The remote to use is the one given on the command line.  It does look for a config section for the given remote.  Let's say you're using - remote-X: in this case, it looks for:
 - [remote "remote-X"]
    url = ...
 - If that section does not exist, or there is no - url =entry, you get an error:- fatal: 'remote-X' does not appear to be a git repository.1  Otherwise that gives the URL, and- git fetchwill attempt to connect to there.  Assuming it can connect...
 - Normally there's also at least one config entry, possibly more, reading: -     fetch = +refs/heads/*:refs/remotes/remote-X/*
 - (the name of the remote is hard-coded here).  Assuming there is... - Next, - git fetchasks the remote what refs it has (branches and tags mostly, although you can get all refs, but most people just care about branches and tags).  You can do this same thing yourself with- git ls-remote remote-X, which spills out stuff like this:
 - 676699a0e0cdfd97521f3524c763222f1c30a094        HEAD
222c4dd303570d096f0346c3cd1dff6ea2c84f83        refs/heads/branch
676699a0e0cdfd97521f3524c763222f1c30a094        refs/heads/master
 - The treatment of the - HEADref is not entirely consistent (I've seen it behave oddly) but usually here it just gets dropped.2  The remaining branches are renamed and updated according to the- fetch =refspec.  (If there are multiple- fetch =refspecs, they're renamed and updated according to all of them.  This is mainly useful for bringing over- refs/notes/or making your own "remote tags" name-space under- refs/rtags/, for instance.)
 - In this case, fetch will bring over any objects needed for the two branches - branchand- master, and update the (local) "remote branch" names,- refs/remotes/remote-X/branchand- refs/remotes/remote-X/master, as needed.  For each one that is updated,- fetchprints a line like this:
 -    22b38d1..676699a  master     -> remote-X/master
 - If the - fetch =lines are missing, you get something quite different.  The output will read:
 -  * branch            HEAD       -> FETCH_HEAD
 - In this case, it's as if the (missing) - fetch =line were there and contained- fetch = HEAD.
 
- git fetch remote refspec(the- refspecpart is one or more refspecs, really, as described below).
 - This is similar to case 2, only this time, the "refspecs" are supplied on the command line, instead of from the - fetch =configuration entries for the remote.  However, the fetch behavior is pretty different here.
 
Let's pause a moment and describe a refspec properly, in this particular case.  (Refspecs also occur for git push but, as usual with git, implementation details leak out and they work slightly differently there.)  A refspec has an optional leading plus (+) sign, which I'll ignore here;3 then two parts, separated by a colon (:).  Both are often just a branch name, but you can (and fetch = lines do) spell out the "full" ref-name, refs/heads/branch in the case of a branch name.
For fetch operations, the name on the left is the name on the remote itself (as shown by git ls-remote for instance).  The name on the right is the name to be stored/updated in your local git repository.  As a special case, you can have an asterisk (*) after a slash as the last component, like refs/heads/*, in which case the part matched on the left is replaced on the right.  Hence refs/heads/*:refs/remotes/remote-X/* is what causes refs/heads/master (as seen on the remote, with git ls-remote) to become refs/remotes/remote-X/master (as seen in your local repository, and in shorter form, on the right side of the -> line git fetch prints).
If you don't put in the :, though, git fetch has no good place to put a copy of "the branch over there".  Let's say it's going to bring over the remote's refs/heads/master (the master branch on the remote).  Instead of updating your refs/heads/master—obviously that would be bad if you have your own commits in branch master—it just dumps the update into FETCH_HEAD.
Here's where things get particularly squirrely.  Let's say you run git fetch remote-X master branch, i.e., give at least one, and maybe several, refspecs, but all with no colons.
- If your git version older than 1.8.4, the update only goes into - FETCH_HEAD.  If you gave two colon-less refspecs,- FETCH_HEADnow contains two lines:
 - 676699a0e0cdfd97521f3524c763222f1c30a094        branch 'master' of ...
222c4dd303570d096f0346c3cd1dff6ea2c84f83        branch 'branch' of ...
 
- If your git version is 1.8.4 or newer, the update goes there—this part is unchanged—but also, the fetch takes the opportunity to record these branches permanently in their proper remote branches, as given by the - fetch =lines for the remote.
 - For whatever reason, though, - git fetchonly prints out an update- ->line for the remote branches that are actually updated.  Since it always records all the updates in- FETCH_HEAD, it always prints the branch names here.
 - (The other issue, besides needing git 1.8.4 or newer, with getting the remote branches updated is that those - fetch =lines must exist.  If they don't, there's no mapping by which the fetch knows to rename- refs/heads/*to- refs/remotes/remote-X/*.)
 
In other words, git 1.8.4 and newer really does "opportunistically update" all the remote branches.  Older versions of git do it on git push, so it has been inconsistent before.  Even in git 1.8.4 it's still inconsistent with git pull, I think (although I don't use git pull enough to notice :-) ); that's supposed to be fixed in git 1.9.
Now let's get back to the difference between git fetch remote and git fetch remote refspec ....
- If you run - git fetch remote, i.e., omit all the refspecs, the fetch falls back to the- fetch =lines as usual.  The fetch operation brings over all the refs from the- fetchlines.  All of these go into- FETCH_HEAD, but this time they're marked "not-for-merge" (with tabs, which I changed to one space to fit on the web pages better):
 - 676699a0e0cdfd97521f3524c763222f1c30a094 not-for-merge branch ...
 - Refs that are not branches, e.g., - refs/notes/refs that are brought over, read instead:
 - f07cf14302eab6ca614612591e55f7340708a61b not-for-merge 'refs/notes/commits' ...
 - Meanwhile, remote branch refs are updated if necessary, with messages telling you which ones were updated: -    22b38d1..676699a  master     -> remote-X/master
 - Again, everything gets dumped into - FETCH_HEAD, but only refs that "need updates" are updated and printed.  New branches get the "new branch" printed and old ones have their abbreviated old-and-new SHA-1 printed, as for- master -> remote-X/masterabove.
 
- If, on the other hand, you run - git fetch remote refspec ..., the fetch brings over only the specified refspecs.  These all go into- FETCH_HEADas usual,6 but this time every one of them is printed.  Then, if your git is 1.8.4 or newer, any reference-updates that can be mapped (via sensible- fetch =lines) and need updating are also updated and printed:
 -  * branch            master     -> FETCH_HEAD
 * branch            branch     -> FETCH_HEAD
   22b38d1..676699a  master     -> remote-X/master
 - If your version of git is older than 1.8.4, the update of - remote-X/masterdoes not occur for this case—or rather, it does not occur unless one of your command-line refspecs was- refs/heads/master:refs/remotes/remote-X/master, or- refs/heads/*:refs/remotes/remote-X/*, or the variants of those with the plus-signs in front.
 
1This is not a great error message.  The remote-X argument was never supposed to be a "repository", it was supposed to be a "remote"!  It might be nice if git said something more informative here.
2There's a flaw in the git remote protocol: HEAD is usually an indirect ref as it's the current branch on the remote, so it should come over as "ref: refs/heads/master" for instance, but instead it comes over as the fully resolved SHA-1.  At least one git command (git clone) attempts to "guess" the current branch on the remote by comparing this SHA-1 to that of each branch-head.  In the above, for instance, it's clear that the remote is "on branch master", as HEAD and refs/heads/master have the same SHA-1.  But if multiple branch names point to the same commit, and HEAD matches that commit-ID, there's no way to tell which branch (if any) HEAD is on.  The remote could be in "detached HEAD" state too, in which case it's not on any branch, regardless of SHA-1 values.
Edit, 2019: this bug was fixed in Git version 1.8.4.3.  As long as both Git versions—on the machine you're cloning from, and on your own machine—are 1.8.4.3 or newer, Git no longer has to guess.
3The plus sign means "accept forced updates", i.e., take updates that would be rejected by the "nothing but fast forward"4 rule for branches, or "never change tags"5 for tags.
4A "fast forward" for a label, changing it from an old SHA-1 to a new one, is possible when the old SHA-1 in the commit Directed Acyclic Graph is an ancestor of the new SHA-1.
5The "never change tags" rule was new in git 1.8.2.  If your git is older than that, git uses the branch rules for tags too, allowing fast-forwarding without "forced update".
6But without the not-for-merge this time.  Basically, when you supply colon-less refspecs, git fetch assumes they're "for merge" and puts them into FETCH_HEAD so that git merge FETCH_HEAD can find them.  (I have not tested what happens with non-branch refs.)