How to reorder a legend in ggplot2?

I find the easiest way is to just reorder your data before plotting. By specifying the reorder(() inside aes(), you essentially making a ordered copy of it for the plotting parts, but it's tricky internally for ggplot to pass that around, e.g. to the legend making functions.

This should work just fine:

df$Label  <- with(df, reorder(Label, Percent))
ggplot(data=df, aes(x=Label, y=Percent, fill=Label)) + geom_bar()

I do assume your Percent column is numeric, not factor or character. This isn't clear from your question. In the future, if you post dput(df) the classes will be unambiguous, as well as allowing people to copy/paste your data into R.

With the data you provided, the following works for me basically applying the suggestion from Frank:

Labels <- c("G", "G", "A", "C", "M", "B", "M", "G", "A","M")
Percent <- c("-0.241","-0.046", "-0.037", "-0.024", "-0.003","0.007","0.01","0.059","0.121", "0.152")
df <- data.frame(Labels, Percent)
df$Percent <- as.numeric(as.character(df$Percent))
legend_ord <- levels(with(df, reorder(Labels, Percent)))

library(ggplot2)
p <- ggplot(data=df, aes(x=reorder(Labels, Percent), y = Percent, fill=Labels)) 
p <- p + geom_bar(stat="identity")
p + scale_fill_discrete(breaks=legend_ord)

Regarding your followup question, if you have specific colors you can assign them within the scale_fill_manual call.

p <- ggplot(data=df, aes(x=reorder(Labels, Percent), y = Percent, fill=Labels)) 
p <- p + geom_bar(stat="identity")
p + scale_fill_manual(breaks=legend_ord, 
    values=c("G"="#0000FF", "C"="#003FBF","B"="#007F7F","A"="#00BF3F","M"="#00FF00"))