How to add edge labels in Graphviz?

You use the label property attached to the edge.

digraph G {
 a -> b [ label="a to b" ];
 b -> c [ label="another label"];
}

The above generates a graph that looks something like this.