Sorry for resurrecting an old thread, but I was with the same problem today. The simplest way that I have found is the following:
# Expand right side of clipping rect to make room for the legend
par(xpd=T, mar=par()$mar+c(0,0,0,6))
# Plot graph normally
plot(1:3, rnorm(3), pch = 1, lty = 1, type = "o", ylim=c(-2,2))
lines(1:3, rnorm(3), pch = 2, lty = 2, type="o")
# Plot legend where you want
legend(3.2,1,c("group A", "group B"), pch = c(1,2), lty = c(1,2))
# Restore default clipping rect
par(mar=c(5, 4, 4, 2) + 0.1)
Found here: http://www.harding.edu/fmccown/R/