Why does git merge with no conflicts still produce a merge commit?

Question 1

The short answer is that a commit records a specific state of your working directory, and a merge will create a state that doesn't match either of the parents, so a new commit is required, as opposed to just moving a branch pointer. To elaborate a bit more, though, it helps to understand exactly what it means to merge two branches.

The two most common ways git merge is used are to a) catch up a local branch to a remote branch and b) actually merge two separate branches together.

In the first case, you have something like this:

A--B--C--D--E--F--G
      ^           ^
      |           +-- origin/master
      +-- master

In this case, git merge origin/master simply moves the pointer for master to the new location. This is what's called a "fast forward" merge, and usually does not result in a new commit (although you can explicitly request one if you have a reason to).

On the other hand, if you have something like this:

A--B--C--D--E--F--G <-- branch1
      \
       J--K--L--M--N <-- branch2

and you are on branch2 and want to merge in branch1, simply moving your branch2 pointer would not make sense. If you just moved branch2 to point to G, you would lose the changes made in J through N. In this case git merge must create a new commit, where the resulting working tree would look like you took a copy of C (the merge base of G and N, which you can see by running git merge-base branch1 branch2), and then applied all of the changes in D through G and in J through N. Even if this results in no conflicts (the two branches either modified different sets of files or at least just different areas of the files), the resulting working directory state does not match either G or N, so a new commit is required. So git will create a new commit with a working directory that contains the results of applying the changes from both branches, and will mark that commit as having both G and N as parents.

So, it's not really "storing the information that there were no conflicts", it's storing a new unique state of your project. Sure, you can look at that commit with git log, git diff, etc. and see that either there were or weren't conflicts, but that's not the reason the new commit was made.

Question 2

The point of a merge commit is to include two different trees of commits in the parent of the resulting HEAD.

There are three possible ways to perform a merge:

Create a merge commit with a separate parent for each thing you merged.
This means that all of the original commits from the branch you merged will still show up in your history as a separate parallel track.
Create a fake merge commit with only one parent which contains all of the merged changes.
This results in a simpler history (no separate tree), but it loses all of the commits of the merged branch.
This is a bad idea.
Create new commits for the merged changes which have the original branch as their parents.
This results in a linear history with both sets of commits interspersed.
This is what git rebase does.

Question 3

Is storing the information that there were no conflicts really worth the extra clutter to the revision history?

You want git rebase, which does this. One simple way to think of using rebase to merge and avoid a merge commit is, "pretend that work happened first instead of in parallel."

Rebase can be dangerous to "play with" before git makes sense to you as elegant, but it does solve the problem you have intuited. In general rebase is used when the "raw" commit history does not make sense to you. In the case of a merge, it's used when one of the parent histories you think is irrelevant and should never have really happened (it "rewrites history"). In the case of some major merges, you really do want both histories; in others, you don't. I'm omitting a fuller explanation as you can find many online, some better than others.