What's the difference between 'git merge' and 'git rebase'?

Suppose originally there were 3 commits, A,B,C:

Then developer Dan created commit D, and developer Ed created commit E:

Obviously, this conflict should be resolved somehow. For this, there are 2 ways:

MERGE:

Both commits D and E are still here, but we create merge commit M that inherits changes from both D and E. However, this creates diamond shape, which many people find very confusing.

REBASE:

We create commit R, which actual file content is identical to that of merge commit M above. But, we get rid of commit E, like it never existed (denoted by dots - vanishing line). Because of this obliteration, E should be local to developer Ed and should have never been pushed to any other repository. Advantage of rebase is that diamond shape is avoided, and history stays nice straight line - most developers love that!

I really love this excerpt from 10 Things I hate about git (it gives a short explanation for rebase in its second example):

3. Crappy documentation

The man pages are one almighty “f*** you”¹. They describe the commands from the perspective of a computer scientist, not a user. Case in point:

git-push – Update remote refs along with associated objects

Here’s a description for humans:

git-push – Upload changes from your local repository into a remote repository

Update, another example: (thanks cgd)

git-rebase – Forward-port local commits to the updated upstream head

Translation:

git-rebase – Sequentially regenerate a series of commits so they can be 
             applied directly to the head node

And then we have

git-merge - Join two or more development histories together

which is a good description.

---

^{1. uncensored in the original}

Personally I don't find the standard diagramming technique very helpful - the arrows always seem to point the wrong way for me. (They generally point towards the "parent" of each commit, which ends up being backwards in time, which is weird).

To explain it in words:

• When you rebase your branch onto their branch, you tell Git to make it look as though you checked out their branch cleanly, then did all your work starting from there. That makes a clean, conceptually simple package of changes that someone can review. You can repeat this process again when there are new changes on their branch, and you will always end up with a clean set of changes "on the tip" of their branch.
• When you merge their branch into your branch, you tie the two branch histories together at this point. If you do this again later with more changes, you begin to create an interleaved thread of histories: some of their changes, some of my changes, some of their changes. Some people find this messy or undesirable.

For reasons I don't understand, GUI tools for Git have never made much of an effort to present merge histories more cleanly, abstracting out the individual merges. So if you want a "clean history", you need to use rebase.

I seem to recall having read blog posts from programmers who only use rebase and others that never use rebase.

Example

I'll try explaining this with a just-words example. Let's say other people on your project are working on the user interface, and you're writing documentation. Without rebase, your history might look something like:

Write tutorial
Merge remote-tracking branch 'origin/master' into fixdocs
Bigger buttons
Drop down list
Extend README
Merge remote-tracking branch 'origin/master' into fixdocs
Make window larger
Fix a mistake in howto.md

That is, merges and UI commits in the middle of your documentation commits.

If you rebased your code onto master instead of merging it, it would look like this:

Write tutorial
Extend README
Fix a mistake in howto.md
Bigger buttons
Drop down list
Make window larger

All of your commits are at the top (newest), followed by the rest of the master branch.

(Disclaimer: I'm the author of the "10 things I hate about Git" post referred to in another answer)