Before I replaced mine, I stripped with a water-based paint remover (no fumes) and then gently scrubbed dirty areas with soap and water to get the dirt out.
FWIW,
The PO of my E38 refinished the sole using the same method that Geoff described and it came out quite nice. Its not perfect, there are some watermarks, stains, etc. but it is still presentable and likely better than it was. Depends on how perfect you want it. RT
In my answer, I assumed your sole, like mine, could not be removed from the boat. If it can be removed I would recommend taking it home, stripping, cleaning, and coating all sides with penetrating epoxy before refinishing.
Will,
You might want to do a Search on this site using words like 'cabin sole' -- pages of info and pictures to look over. As these boats all get to (and beyond) 20 years, everyone wants to protect and then bring back that "new look" to the teak and holly sole pieces.
Here is a current picture of a portion of ours, about 7ish years after the last time it was re-varnished... Dull but still a lot nicer than the mess of old oil, mold, gouges, and ground-in dirt that was there when we bought the boat in '94.