Firstly, in connexion with optics, Fermat's principle is always and approximation: it defines an approximation, namely the first term in the WKB Approximation to the solution of either the quasi-time-harmonic Maxwell's equations or, in a more general setting, the Helmholtz equation. Here the WKB scale parameter is the wavelength, which is taken to be small compared to the features of a medium in question. As explained beautifully in CR Drost's Answer, the intuition behind this is that Fermat's principle defines paths of stationary phase around which diffraction effects are added to get the complete solution to the problem and is extremely widely applicable without approximation, i.e. Fermat's principle will give, without approximation, the first term in the relevant WKB expansion in all the situations discussed below. These include all special relativistic (flat spacetime) problems and static general relativistic ones too.
The extremized quantity, or the optical Lagrangian, is the optical path length expressed as a phase difference between the ends of the ray path - in waves or radians, for example. A careful reading and mulling over CR Drost's answer clearly shows this fact. So it is not probably not helpful to think of it as least time principle since, as in Michael Siefert's answer this is can be problematic in relativity. In contrast, the phase field of a steady state optical excitation in a medium is a scalar field i.e. it transforms as such.
In Special Relativity, one can see how the principle plays out in two different, relatively boosted inertial frames by looking at the steady-state optical field in question from the two different frames at the instant when the origins of their co-ordinate systems co-incide. Let's put one of the frames at rest relative to the material mediums that the field is established in. Fermat's principle plays out in the wonted way in this frame.
The relatively moving observer sees the medium in Lorentz-transformed co-ordinates. Maxwell's equations are still Lorentz covariant with the medium present, but the medium properties and the constitutive relationships transform radically. Intuitively you can see this is so; the Lorentz Fitzgerald contraction changes the medium's optical density anisotropically. In fact, if we have a simple, anisotropic medium in the rest frame with electric and magnetic constants $p_e$ and $p_m$ (One shuns epsilons and mus in these kinds of calculations to avoid confusion with Greek indices on tensors), the relatively moving observer sees an anisotropic magnetoelectric constant such that:
$$\vec{D} = p_e\,\vec{E} + c^{-1} \vec{v}\times \vec{H}$$
$$\vec{B} = p_m\,\vec{H} - c^{-1} \vec{v}\times \vec{E}$$
where, naturally, $\vec{v}$ is the relative velocity.
The upshot of all of this is that both observers calculate the same scalar phase field from their version of Maxwell equations and so a ray path is an extremal optical path length path in one frame if and only if it is an extremal path in the other. So we see that the Fermat principle gives us the same rays in both cases.
A quirk here is that, in the anisotropic medium as seen by the relatively moving observer, Snell’s law does not apply to rays at interfaces, although it does apply to wave vectors. Phase fronts are not needfully normal to the Poynting vectors. This is the same situation as in an anisotropic crystal. But Fermat’s principle still applies.
In General Relativity we must be a little careful. The optical Fermat principle applies time-invariant mediums. Therefore, it cannot be applied (at least I am not aware of any extension) to nonstatic spacetime - or at least one without a timelike Killing field - with or without material mediums. This is because, in the first instance, Fermat's principle applies to time-harmonic electromagnetic fields, with pulses and the like being described by Fourier superpositions of time-harmonic solutions;
But for a static, curved spacetime, the situation is similar to the special relativistic one. Different observers see a medium’s material properties and constitutive differently, but such that they would all agree on the scalar phase field for a given steady state optical excitation of the medium, and they would all calculate the same ray paths from the Fermat principle.
In fact, an empty, medium-less curved spacetime has the constitutive relationships (Plebanski's constitutive equations, see J. Plebanski Phys. Rev. 118 (1960), p1396:
$$D^i = -\epsilon_0\,\frac{\sqrt{-g}}{g_{0 0}}\,g^{i j}\,E_j + c^{-1} \varepsilon^{ij}_{\,\,k}\,\frac{g_{0j}}{g_{00}}H^k$$
$$B^i = -\mu_0\,\frac{\sqrt{-g}}{g_{0 0}}\,g^{i j}\,H_j + c^{-1} \varepsilon^{ij}_{\,\,k}\,\frac{g_{0j}}{g_{00}}E^k$$
where we have summed over spatial indices $1,\,2,\,3$ only (note the Roman, rather than Greek indices) and the $\varepsilon$ is the three dimensional, spatial Levi-Civita symbol. This observation is the starting point for the field of transformational optics: the use of metamaterial mediums to mimic propagation in the spatially curved part of static curved spacetime. These ideas show great promise for the realization of optical cloaking devices, for example: material mediums whose electric, magnetic and magnetooptic constants match the above propagate light, as does of course empty curved space, without scattering. Light can be bent around objects by such mediums without scattering and it's not too hard to see that the object to be cloaked can be hidden inside regions not reachable from an observer. See, for example:
Ulf Leonhardt and Thomas G. Philbin, "Transformation Optics and the Geometry of Light", Prog. Opt. 53, pp69-152 (2009
