Update: I've posted an improved version of this answer to the Visualizing branch topology in Git question, since it's far more appropriate there. Leaving this answer for historical (& rep, I'll admit) reasons, though I'm really tempted to just delete it.

My two cents: I have two aliases I normally throw in my ~/.gitconfig file:

[alias]
lg1 = log --graph --abbrev-commit --decorate --format=format:'%C(bold blue)%h%C(reset) - %C(bold green)(%ar)%C(reset) %C(white)%s%C(reset) %C(dim white)- %an%C(reset)%C(auto)%d%C(reset)' --all
lg2 = log --graph --abbrev-commit --decorate --format=format:'%C(bold blue)%h%C(reset) - %C(bold cyan)%aD%C(reset) %C(bold green)(%ar)%C(reset)%C(auto)%d%C(reset)%n''          %C(white)%s%C(reset) %C(dim white)- %an%C(reset)'
lg = lg1

git lg/git lg1 looks like this:

and git lg2 looks like this:

(Note: There now exists much more applicable answers to this question, such as fracz's, Jubobs', or Harry Lee's!)

Only the Gods

The great historian was trying to unravel the intricacies of an incorrect merge that had happened many months ago. He made a pilgrimage to Master Git to ask for his help.

"Master Git," said the historian, "what is the nature of history?"

"History is immutable. To rewrite it later is to tamper with the very fabric of existence."

The historian nodded, then asked: "Is that why rebasing commits that have been pushed is discouraged?"

"Indeed," said Master Git.

"Splendid!" exclaimed the historian. "I have a historical record of a merge commit with two parents. How can I find out which branch each parent was originally made on?"

"History is ephemeral," replied Master Git, "the knowledge you seek can be answered only by the gods."

The historian hung his head as enlightenment crushed down upon him.

From https://stevelosh.com/blog/2013/04/git-koans/

Branches are simply moving pointers in the graph of all commits. They can be added and removed without consequence and there is no record of their being there.

The asterisks show where something was committed:

e1193f8, 5a09431 and 30e367c were committed to the left branch (yielding a | on the right branch) whereas 420eac9 was committed to the right branch (yielding a | on the left branch). And that is how 420eac9 differs from the rest: it's the only commit to the right branch.

For the sake of completeness:

• d6016bc was the branching point
• 5e3ee11 is the merging commit
• 2d3acf9 is the first commit after merging

First, one obtains a list of commits (as with git rev-list), and parents of each commit. A "column reservation list" is kept in memory.

For each commit then:

• If the commit has no column reserved for it, assign it to a free column. This is how the branch heads will start.
• Print the tree graphics according to the column reservation list, and then the commit message
• The reservation's list entry for the current column/commit is updated with the first parent of the current commit, such that the parent is going to be printed in the same column.
• Other parents get a new free column.
• If this was a merge, the next line will try to link the second parent to a column where the commit is expected (this makes for the loops and the "≡ bridge")

Example showing output of git-forest on aufs2-util with an extra commit to have more than one branch).

With lookahead, one can anticipate how far down the merge point will be and squeeze the wood between two columns to give a more aesthetically pleasing result.