You don't have to label the edges. the problem in your approach is that you tell the graph to use String as edge type. A proper std. way of doing things would be:
SimpleGraph<String, DefaultEdge> sg = new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);
sg.addVertex("A");
sg.addVertex("B");
sg.addVertex("C");
sg.addEdge("A", "B");
sg.addEdge("B", "C");
System.out.println("graph: " + sg.toString());
System.out.println("edges of A: " + sg.edgesOf("A"));
System.out.println("edges of B: " + sg.edgesOf("B"));
this will give you the following output:
graph: ([A, B, C], [{A,B}, {B,C}])
edges of A: [(A : B)]
edges of B: [(A : B), (B : C)]
So to fix the problem it is necessary to switch your edge class to DefaultEdge as shown in the code.