The problem here is that legend will only provide labels for what graphics recognizes as individual objects. So in a line plot, each line is recognized as an object - but graph is recognized as one object only (which allows all the nodes and edges to be rearranged when the layout changes).
The output of highlight is not helpful because the highlights aren't a separate object, highlight is just a method which changes the coloring of the nodes and edges of the GraphPlot object.
The best way to achieve the requested plot is the following one (quite messy):
s = [1 1 1 1 1 1 2 3 4 5 6 7 7 7 7 8 9 10 11 8 6];
t = [2 3 4 5 6 7 3 4 5 6 2 8 9 10 11 10 10 11 8 1 11];
G = graph(s,t);
plot([NaN NaN], [NaN NaN], '-')
plot([NaN NaN], [NaN NaN], 'r-')
set(gca, 'ColorOrderIndex', 1)
h = plot(G);
[T,p] = minspantree(G);
legend('standard edges', 'highlighted edges')
The messy part is that the legend is showing objects by the order in which they are plotted - so the objects you want to see in the legend need to be added first.
To do a legend entry for green nodes, use plot([nan nan], [nan nan], 'og', 'MarkerFaceColor', 'rg') (a bit more complicated because plot's circles are usually not filled, while the GraphPlot nodes are always filled).