How to Listen For an Application Launch Event on Mac OS X
You can use a LaunchAgent (see Lingon) to perform an action when a file is modified. Time Machine has some file somewhere that it modifies each time it starts.