Restoring valuable minifigures
First off be very careful of the printing on the minifigure, the plastic is quite durable but the printing can wipe off rather easily. I list a few different methods to remove permanent marker all have their varying degrees of risk. They are listed in the order I'd try them in.


Dry erase marker?! Just cover over the permanent marker with a dry erase marker then wipe it off. yes it works.
Aerosol hairspray, body spray, Rubbing alcohol (Isopropyl alcohol), etc. Like JohnnyB suggested alcohol is a good cleaner for permanent marker, especially on plastic. Just be careful of the printing any alcohol biased cleaner can and will remove the printing.
Nail polish remover. Be very careful with this one, nail polish remover's active ingredient is acetone. Acetone with enough time will dissolve ABS (and rubber tires very quickly) but long before that happens it will remove the printing :( I'd only try acetone as a last resort. 
Toothpaste I'd recommend skipping this social media craze, it may work (on lego) but there are better ways. On the plus side I doubt the toothpaste it will hurt the minifig, however all the scrubbing necessary to remove the marker that is another story...