It's a database that stores a "graph" of vertices that are connected by edges. If you were say, creating the next LinkedIn and you wanted to find the shortest path between two users based on their connections, a graph database would be a good choice.

Let's imagine you want to see how Fred is connected to Steve, their network looks like this:

    [Fred] <-knows-> [Bob]
    [Bob] <-isMarriedTo-> [Sally]
    [Bob] <-knows-> [Alice]
    [Alice] <-workedWith-> [John]
    [John] <-wentToSchoolWith-> [Sandra]
    [Sandra] <-knows-> [Steve]

Diagram: http://yuml.me/6ff3074e

A "traditional" database like MySQL or Mongo makes this kind of query prohibitively expensive and complicated, as it must perform a new join for every connected person in the user's graph.

Graph databases come into their own because they are designed specifically for efficient traversal of these connecting edges. They typically do this by storing "pointers" on each vertex to its connected edges, so while a normal RDBMS requires something like a hash table lookup to resolve a join, a graph database can simply "jump" to the relevant record via a pointer. This means that things like Dijkstra's algorithm [0] can be implemented efficiently.

However, "traditional" graph databases like Neo4j require everything to be structured in terms of vertices and edges. This is often quite inconvenient, so Multi Model databases like ArangoDB integrate this graph approach with a document store as well, the idea being that if you can keep everything in the same db your app gets a lot simpler, you regain things like ACIDity that you'd normally lose by using 2 separate dbs, and performance should be a lot better too.

[0] http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm