How does light know which path is fastest? We know from Fermat's principle of least time that light follows the fastest path. But how does light know which path is the fastest?
 A: The Fermat principle does not say light ray follows the fastest path, it says when there is a light ray, the optical path (length divided by index of refraction) is stationary with respect to small variations in the shape of the ray that preserve the position of the boundary points.
It is not as if light got everywhere the fastest way possible; it goes where directed by the source and surrounding medium. The effect of the medium is such that the resulting path obeys the criterion of stationarity with respect to small variations. In some cases, the optical path is the shortest for the pair of boundary points, in other cases (less common) it is the longest and there may be cases where it is neither (like when stationary point is a saddle point).
A: A way to understand this, is to imagine that light actually follows all paths. However, most paths experience destructive interference with other paths. The only paths that do not experience destructive interference are those in the neighbourhood of paths with stationary (e.g., minimal) action (time).
I strongly recommend reading Feynman's QED: The Strange Theory of Light and Matter. In the link you'll also find a link to video.
A: The premises of your questions are incorrect because you are in fact asking the wrong question. Physics (and science in general, for that matter) does not provide an answer to why things are the way they are, rather it provides an answer to how to make predictions for future experiments. Whenever you ask why something is the way it is, one can address the behaviour to another more fundamental characteristic, this is true, but then you would be asking why this other characteristic behaves the way it does - and so on and so forth until you come to a fundamental point where there is a fundamental property that you just have to accept true.
Light does not choose anything. Optics principles state that an empirically true result is that light paths are such that they minimise the action between them: you assume this is true (because it experimentally is) and use it to make predictions - and then you construct the entire geometry of Optics and the like. Of course you might redirect the principle of least action to the Huygens–Fresnel principle, stating that propagation of light is generated as if each point of a light wavefront acted as a source of a spherical wave; but then again you might ask why the Huygens–Fresnel principle holds true in the first place.
Imagine asking yourself why, in Newton's law, the force is proportional to the acceleration. Why can it not be proportional to the acceleration squared, for instance? The answer is that it could very well be and if it were we would be describing a universe where such law holds true, with all the corresponding consequences. It just happens not to be the case in our current universe.
