"Run on Computer Start" I select this box in OPTIONS then restart my computer. I don't see any evidence of the program running on restart. Should I? When I return to options the box is unchecked. Do I need to check the box every time?
You may need Administrator privileges on your profile to make the setting stay. Or optionally you can input a shortcut into the Startup folder (Start->All Programs->Startup) with these parameters:
"C:\Program Files\CCleaner\ccleaner.exe" /AUTO
About the only good thing about putting it in the Startup folder is that you can cancel it by pressing and holding the left Shift key whilst the startup programs are loading, which is useful if you're installing some software update that it may interfere with by deleting the temporary files.