If you're browser supports custom CSS files (which pretty much every browser does), you can just use the following:

    a[rel~="nofollow"] {
        background-color: rgba(255,0,0,0.10);
        //background-color: rgb(255,0,0);//for people without rgba
    }

Credit to Tom: http://tlrobinson.net/blog/?p=37