Take 'em for a bath. No, seriously! A few years back I picked up a collection that included many of the 12" figures and they exhibited the same general wear and grubbiness you mention. My standard process is with any collection I fill a sink with warm soapy water and hand wash everything, sometimes using a soft toothbrush to get dirt out of crevices. Give everything a quick rinse and let dry.
With the 12" figures I removed the clothes and then handwashed everything with a little laundry detergent. You should find that will remove 99% of the dirt and leave everything looking as good as the day it was made. Most 12" items weren't really heavily played with, as in they weren't usually thrown across back yards, dropped out of trees, etc so a lot of dirt and wear is simply from kid handling.
Be aware though that there are some things you won't easily, if ever, remove. Ink stains, particularly on the soft boots of Luke, Leia, Ben Kenobi, etc are usually there for good. Typically they are a bugger to remove from clothing too.
If you do decide to have a go at this you should take some before and after shots, it would make a great article and public reference for the site!