You're much better off using ggsave to save the figure as a eps or svg, then opening it in Illustrator (or open source equivalent) and replacing the legend with the images. If you're really dead set on doing it all in R, you can use annotation_raster in the current ggplot2 and add in some text next to it using geom_text. Here is a rough attempt:

set.seed(10)
library(ggplot2) 
library(RCurl)
library(png)
df <- data.frame(animal = sample(c("sharks", "tigers"),20, rep=T), time=1:20, 
                 scariness = rnorm(20)*-20)

shark <- readPNG(getURLContent("http://i.imgur.com/EOc2V.png"))
tiger <- readPNG(getURLContent("http://i.imgur.com/zjIh5.png"))

ggplot(df, aes(time, scariness, group = animal, color = animal)) + 
geom_line(show_guide = FALSE) +
 annotation_raster(tiger, xmin = nrow(df)-1, xmax = nrow(df), 
    ymin = max(df$scariness)-(.05*max(df$scariness)), 
    ymax = max(df$scariness), interpolate = T) +
 annotation_raster(shark, xmin = nrow(df)-1, xmax = nrow(df), 
    ymin = max(df$scariness)-(.1*max(df$scariness)), 
    ymax = max(df$scariness)-(.05*max(df$scariness)), interpolate = T)