Change the order in which the plots are added to the figure, and then call legend
normally. That should do it.
You can also do it as follows. First get handles to the individual plots:
h1 = plot(1:5);
hold on
h2 = plot(11:15, 'r');
Then call legend
specifying the order:
legend([h1 h2],'plot1','plot2')
or
legend([h2 h1],'plot2','plot1')