How do render passes work?
"Cycles shoots one ray per pixel and sample from the camera where it
  bounces off from geometry until it hits a light source or gets killed
  by the Light paths settings"


This is what happens in principle. In practice there are all kinds of tricks and optimizations that make path-tracing much faster than the naive implementation described by you. For example shadow rays are shot from the surfaces in the direction of light sources, and a trick assures that the image converges towards the same image as without shadow rays, but much faster. These shadow rays allow us to collect the "direct" and "indirect" lighting information separately. They are always collected separately, the passes just expose this internal information to you. This shadow rays/direct sampling trick is called "next event estimation" in the CG literature, if you want to learn more about it.


  Shadow, AO - How do they affect the final image?


They don't. The information in the shadow pass is already contained in the other passes, and AO is just some kind of fake global illumination, which is not necessary, as path tracing provides physically based GI. 

About your other questions: I guess the answer is also in the Cycles implementation details. Note that (according to the Cycles roadmap) in the future Cycles will have AOVs (Arbitrary Output Variables) instead of hardcoded passes.