Legend on RgoogleMaps?

I use library(RgoogleMaps) to plot measurement-positions on a map (points). There is different equipment on different points, and I successfully get separately colored points per equipment:

theplot <- PlotOnStaticMap(lat=sitecoord$lat, lon=sitecoord$lon, 
                           cex=.7, pch=20, 
                           col=sitecoord$equipmentType, 
                           MyMap=Map, NEWMAP=FALSE)

How can I add a legend to the resulting map-plot to see which equipment is represented by blue points, which by red, and so on?

Update:

Using the very good recommendations of @Rguy. I managed to get the legend in. For the benefit of others, here is my test-code (no, I'm not measuring in Iceland, just used it as example):

library(RgoogleMaps)
library(RColorBrewer)

Equipment <- c("AA","AA","BB","CC")
lat <- c(63.90,66.20,64.80,64.50)
lon <- c(-22.40,-14.20,-18.60,-15.00)
tblDataPoints <- data.frame(Equipment,lat,lon)

My.Pal <- brewer.pal(3, "Reds")
tblDataPoints$colorz <- My.Pal[tblDataPoints$Equipment]

plot.new()
bb <- qbbox(lat=range(tblDataPoints$lat), lon=range(tblDataPoints$lon))
m <- c(mean(tblDataPoints$lat), mean(tblDataPoints$lon))
zoom <- min(MaxZoom(latrange=bb$latR,lonrange=bb$lonR))
Map <- GetMap.bbox(bb$lonR, bb$latR, zoom=zoom, maptype="roadmap", NEWMAP=TRUE)
tmp <- PlotOnStaticMap(lat=lat, lon=lon, cex=.7, pch=20, col=tblDataPoints$colorz, MyMap=Map, NEWMAP=FALSE)

tblLgd <- unique(tblDataPoints[,c("Equipment","colorz")])
row.names(tblLgd) <- NULL

legend("topright", legend = tblLgd$Equipment, fill = tblLgd$colorz, bg = "white")

Solution

I've done this before. If you had made a reproducible example of the problem you're having with the legend function, we could discuss it. Until then, here is a vague explanation.

1. Create a palate using RColorBrewer. For example:

library(RColorBrewer)
My.pal <- brewer.pal(9, "reds")

2. Assign each of your points a color, in some way. In my case, I had a WT column and a vector of bins, and so I generated the colors per point by binning the weights, and taking the cooresponding entry in my.pal to be that point's color. Note that in this example, there are fewer than 9 bins in my binz vector, since my palate has only 9 shades of red.

colorz <- My.Pal[cut(datas$WT, labels = FALSE)]

3. Plot on the map, passing the colors argument.

PlotOnStaticMap(MyMap, lat = datas$LAT, lon = datas$LON, col = colorz)

4. Finally, create the legend, and add it to the map.

legend("bottomleft", legend = legend.txt, fill = My.pal, title = "I AM", bg = "white")

Hope you get it all figured out!