mhh, not in all cases will the program be installed. I've used it on many clients computers and half the time the programs stayed put. If any of the programs were removed, the profile settings, logs, etc will remain although you'll have to install the program again to use 'em.
*edit*
From windows:
-If a program was installed after the restore point that you are restoring to was created, the program might be uninstalled as part of the restoration process. Data files that are created with the program are not lost. However, in order to open the files again, you must reinstall the associated program.
-System Restore does not replace the process of uninstalling a program. To completely remove the files installed by a program, you must remove the program using Add or Remove Programs in Control Panel or the program's own uninstall program. To open Add or Remove Programs, click Start, click Control Panel, and then click Add or Remove Programs.