Label multiple edges between same vertices

Update 3: Styling and labeling edges individually can now be more conveniently done using new-in-version-12.1 function EdgeTaggedGraph:

labels = {"A", "B", "C", "D", "E", "F"};
edges = {a -> b, a -> b, a -> b, a -> b, a -> e, e -> b};
styles = ColorData[97] /@ Range[6];

labelededges =  MapThread[Style[Labeled[#, #2], #3] &, {edges, labels, styles}] ;

EdgeTaggedGraph[labelededges, EdgeLabels -> "Name", 
 ImageSize -> Medium, EdgeLabelStyle -> 16]

Update 2: Dealing with the issue raised by @Kuba in the comments:

Using the function LineScaledCoordinate from the GraphUtilities package to place the text labels:

Needs["GraphUtilities`"]

labels ={"A", "B", "C", "D", "E", "F"};

Graph[{a -> b, a -> b, a -> b, a -> b, a -> e, e -> b},  
EdgeShapeFunction -> 
  ({Text[Last[labels = RotateLeft[labels]], LineScaledCoordinate[#, 0.5]], Arrow@#} &),
VertexLabels->"Name"] 

Update: Using EdgeShapeFunction:

labels = Reverse @ {"A","B","C","D"};
i = 1;
Graph[{a -> b, a -> b, a -> b, a -> b},
 EdgeShapeFunction- > ({Text[labels[[i++]], Mean @ #],Arrow @ #}&)]

---

Simplest method to convert a Graph g to Graphics is to use Show[g] (see this answer by @becko).

We can post-process Show[g] to modify the Text primitives:

Show[Graph[{Labeled[a->b,"A"],Labeled[a->b,"B"]}]]/. 
   Text["A",{x_,y_/; (y<0.)},z___]:>Text["B",{x,y},z]

Or, we can construct a Graph with modified edge directions (and correct labels) and post-process it to change the edge directions:

Show[Graph[{Labeled[a->b,"A"], Labeled[b->a,"B"]}]]/. 
  BezierCurve[{{-1.,0.},m__,y_}]:>BezierCurve[{{1.,0.},m,{-1.,0.}}]
(* same picture *)

This ****, and so does my answer, but if it works it's not stupid, right? :)

p = Graph[{Labeled[a -> b, "A"], Labeled[a -> b, "B"]}];

grp = GraphComputation`GraphConvertToGraphics[p];

ReplacePart[grp, Position[grp, "A"][[1]] -> "B"]

It appears that in Mathematica 10.0.2 Graph does not natively support this by way of wrappers such as Labeled. Note that each of these wrappers is converted to a canonical form that seems to support only one directive for each edge:

Table[
  InputForm @ Graph[{fn[a -> b, "A"], fn[a -> b, "B"]}],
  {fn, {Labeled, Annotation, Tooltip, Style, Hyperlink, EventHandler, Button}}
] // Column

Graph[{a, b}, {DirectedEdge[a, b], DirectedEdge[a, b]},
 {EdgeLabels -> {DirectedEdge[a, b] -> "A"}}]

Graph[{a, b}, {DirectedEdge[a, b], DirectedEdge[a, b]},
 {Properties -> {DirectedEdge[a, b] -> {Annotation -> "A"}}}]

Graph[{a, b}, {DirectedEdge[a, b], DirectedEdge[a, b]},
 {Properties -> {DirectedEdge[a, b] -> {Tooltip -> "A"}}}]

Graph[{a, b}, {DirectedEdge[a, b], DirectedEdge[a, b]},
 {EdgeStyle -> {DirectedEdge[a, b] -> {"A"}}}]

Graph[{a, b}, {DirectedEdge[a, b], DirectedEdge[a, b]},
 {Properties -> {DirectedEdge[a, b] -> {Hyperlink -> "A"}}}]

Graph[{a, b}, {DirectedEdge[a, b], DirectedEdge[a, b]},
 {Properties -> {DirectedEdge[a, b] -> {EventHandler -> "A"}}}]

Graph[{a, b}, {DirectedEdge[a, b], DirectedEdge[a, b]},
 {Properties -> {DirectedEdge[a, b] -> {Button -> Unevaluated["B"]}}}]