If you want to spend the time to clean it:
Hot Scrape. Put on a layer of wax and then scrape it off right away while it is still warm, this will clean your deck and you can then do a regular wax.
Avoid "Base Cleaners" if you can. They strip off everything. Use only for such things as cat grease or pine tar and only spot clean
Get it. Wax it. Ride it.