For what it's worth, here is my updated understanding:
A Provisioning profile is a file that tells you which apps (via an AppID), signed by which developer (via the certificate) can run on which devices (the UDIDs).
With certificates, there is a concept of a public and private key. Public and private keys are mathematically linked such that one can encrypt the plain text, and one can decrypt the cipher text. Certificates allow apple to ensure two things: 1, that only registered developers can distribute their code, and 2, that the code that is being distributed isn't altered on its way to your device.
When you build your code in Xcode, you 'code sign' your application with the private key located in your keychain, thereby 'locking' it. In order to unlock/decrypt the code, the destination device must have access to your public key. The device gets the public key from your certificate that is included in the provisioning profile.
In order to verify that the code remains unchanged on its way from the developer to the device, your certificate includes an algorithm that can convert your code/data into what is known as a 'digest.' On the developer side, the data/code is run thru the algorithm, generating into a separate digest, which is then locked with the private key.
When the app package is received by the device, the device can ensure the code hasn't been altered by doing the following: unlocking the digest with the private key, running the unencrypted data thru the algorithm (remember, the device can access the cert thru its prov profile), and making sure the result is a digest identical to the one sent over from the developer.
Beyond that, the prov profile need only check the UDID of the phone, and make sure the AppID from the profile matches the identifier in the app.
The reason we don't need separate prov profiles for apps from the appstore, i assume, is because each iPhone ships with the public key used by apple to code sign distribution apps.