Is this decompression performed each and every time an app is run, assuming it has been pushed out of Android's process cache?
Yes, and no. Android apps are not decompressed into the file system when it needs to run. Instead, they are selectively decompressed and read into memory/ram by the Dalvik virtual machine. This decompression is a very simple, quick, non-processor-intensive process, so it does not add any real overhead to the system. On first install, there is some optimization by the Dalvik VM, mainly linking to native libraries on the Android system to the internal APK libraries, and this is saved into the Dalvik-cache as an optimized dex file (.odex)
[Side note, this is why the first boot of a phone takes longer, as the system has to create odex files for any app that does not have an odex file. System Apps are typically made to have an odex by the manufacturer]
An APK has a predefined structure, including file lists, resources, assets, libraries, dex (Java Class files converted into Dalvik Executable Format) etc. The system decompresses and reads these files into memory, and follows the code inside. That code tells it when to decompress and load the other files.
It never hits the hard drive, goes right into memory.