In .NET, you could probably create a shell extension which you would register for EXE programs which would really just be a filter for the EXE extension. When your shell extension is called, you would execute the program (by invoking the old functionality) after you logged your information.
Note, however, that you can ONLY do this with .NET 4.0 or above, which is currently in beta. Because of the way that previous versions of the CLR worked, only one version was allowed to run in a process at a time (including explorer, the OS process).
.NET 4.0 introduces Side-by-Side (SxS) CLR instances within the same process, so it is safe to use it from .NET 4.0 on as a mechanism for shell extensions.
It will also require a good deal of COM interop, but it can be done.
In regards to LWoodyiii's comment asking if this can be done in older versions of .NET: Could it? Yes, it can be done, but the official decree from MS is that you shouldn't. The reason for this is because if someone else decides to run a shell extension, or interface with the OS in some way using .NET, and the version is different from the one that you are using, you run the risk of hosing the OS process.