How does Fermat's principle make light choose a straight path over a short path? 
This is a thought experiment where I have made a "C" shaped hole inside diamond. The refractive index $(\mu)$ of diamond is 2.45. Say we shine a laser from top of the "C" as shown.
My calculations show that light reaching A can reach B in the least possible time if gone through the "C". but I'm pretty sure the perpendicular laser beam travels undeflected and straight down. Though I don't have experimental evidence, I see something wrong either with my intuition or with the theory.
It would be great if someone could clarify.
*       'a' in the diagram is the thickness of the cutout and all comparable distances can be taken 'a'.
 A: As others have said, Fermat's principle says that the path which light follows is stationary rather than a minimum of optical path length (though in fact it typically is a bona fide local minimum).  The more important point, however, is that this is a necessary but not sufficient condition for a given path to be that followed by light.  This is a mathy way of saying that there might be several paths which are local extrema of path length, but light need not follow all of them.
This is a typical issue with variational arguments.  The same thing can happen with a massive particle which has the option of following either of two paths to an endpoint.  Feynman considered such scenarios in developing his path integral approach to quantum mechanics, but even for classical mechanics it is an interesting case study.  If you solve the Euler-Lagrange equation for such a system, you'll find that there are two paths which make the action stationary, i.e. two paths which the particle can follow to get from its starting point to its ending point.  But we know that a classical particle will only follow one path, so which will it take?

Mathematically, the issue here is that variational problems are typically posed as boundary value problems⁠—we specify where the particle needs to start and where it needs to end up.  Unlike initial value problems, boundary value problems need not have unique solutions.  But in real life, we don't actually control where the particle ends up.  What we really control is the particle's initial position and velocity⁠—i.e. we set up an initial value problem, a differential equation for which there is a unique mathematical solution.  After we send off the particle and see where it ends up, we can then use its ending location and the Euler-Lagrange equation to see which path it took to arrive at the endpoint, but there can be multiple solutions.
The same thing happens in optical systems.  When you shoot a laser, you specify the initial conditions of the laser beam by the position of the laser and the direction it points.  This sets up an initial value problem which has a unique solution.  After you find out where the beam goes, you can then use the starting and ending points of the beam together with Fermat's principle to figure out the path it took to get there.  But you may find that there are multiple solutions to Fermat's principle, and you need to use either common sense or some discrete data about the orientation of the laser to figure out which one is the right one.

Some final remarks about the particular case you are considering.  The actual shortest path in the system drawn in the OP would be that going straight from point A to the inside corner of the "C", then down the boundary between air and diamond to the other corner, then straight to point B.  A curious feature of this path is that infinitesimal perturbations to the segment of the path along the boundary of air and diamond would result in discontinuous changes in the path length, because if you push the path from the air side to the diamond side the length gets 2.45 times longer.  This means that usual variational calculus arguments (like those used in deriving the Euler-Lagrange equation) don't work, as they assume smooth variation of the action (i.e. optical path length) with small perturbations to the path.  So you have to be more careful in this case.  In fact, physically no light will typically ever follow this path (at least at the level of geometric optics), because there is nothing to "bend the light around the corner".
Another interesting feature of this system is that there might (depending on exact positions of A and B) be another locally extremal path from A to B, namely that which enters the diamond at an angle, undergoes total internal reflection at the air-diamond interface, and then bounces back to B.  So if you have a light bulb (which sends light in all directions) at point A and someone sitting at point B, the person at B would see two lights, one from the line straight to A and another coming at an angle from the left.  This is another illustration of the caveats on Fermat's principle⁠—if the light does not have a well defined initial direction, it may follow multiple stationary paths!

A: As the Wikipedia article on Fermat's principle states in its introduction, this principle, like the principle of "least" action, is properly stated not as light taking the path with the least time taken but one with stationary time with respect to variations of the path.
A: TL;DR: This is basically because Fermat's principle is strictly speaking a principle of stationary time rather than least time. Note that stationary paths between 2 points need not be unique nor exists. Light in principle travels along all stationary paths.
In more details: Assume for technical reasons that the refractive index $n({\bf r})$ is a smooth function of position ${\bf r}$. (In particular, transitions between 2 media are modelled as smooth. Think e.g. of an optical fiber with a smooth gradual fusing of the cladding. Let us also assume that there are no mirrors in the set-up for simplicity.)
Then the optical system can be modelled as a connected 3D Riemannian manifold $(M,g)$, where the metric tensor $g$ is given by (infinitesimal) optical path length.
(The metric tensor $g$ should not be confused with the metric tensor that yields usual 3D Euclidean distances.)
Stationary paths become (not necessarily length-minimizing) geodesics wrt. the metric $g$. Let us furthermore assume that the $(M,g)$ is geodesically complete, so that we can apply the Hopf–Rinow theorem, which implies that any 2 points have a length-minimizing geodesic.
Returning to OP's title question, imagine that there exists a (not necessarily stationary) path $\gamma_1$ that has shorter optical length than some stationary path $\Gamma_2$, cf. OP's figure. Then we know that there exists a stationary path $\Gamma_1$ that also has shorter optical length than $\Gamma_2$.
A: Fermat's principle does not say shortest time. It says that the time taken along the ray is stationary under small perturbations of the path.
Reflections off a concave mirror, for example, produce a local saddle point where the travel time time increases with some changes, decreases with others, but always only at second-order in the magnitude of the change in the ray trajectory.
