Why does gravity travel at the speed of light?
Yes, GR predicts luminal propagation of gravitational waves, by now confirmed in LIGO. Linearized gravity is an adequate approximation to general relativity: the spacetime metric, $g_{ab}$, may be treated as deviating only slightly from a flat metric, $\eta_{ab}$, \begin{equation} g_{ab} = \eta_{ab} + h_{ab},\qquad ||h_{ab}|| \ll 1\;. \end{equation} The resulting Einstein tensor then is $$ G_{ab} = R_{ab} - \frac{1}{2}\eta_{ab} R \\ = \frac{1}{2}\left(\partial_c\partial_b {h^c}_a + \partial^c \partial_a h_{bc} - \Box h_{ab} - \partial_a\partial_b h -\eta_{ab}\partial_c\partial^d {h^c}_d + \eta_{ab} \Box h\right)\;. $$
In terms of the trace-reversed perturbation $\bar h_{ab} = h_{ab} - \frac{1}{2}\eta_{ab} h$, this reduces to $$ G_{ab} = \frac{1}{2}\left(\partial_c\partial_b {{\bar h}^c}_{\ a} + \partial^c \partial_a \bar h_{bc} - \Box \bar h_{ab} -\eta_{ab} \partial_c\partial^d {{\bar h}^c}_{\ d}\right)\;.$$
In Lorenz gauge, this can be further hacked down to $$ G_{ab} = -\frac{1}{2}\Box \bar h_{ab}\;, $$ a relativistic wave equation in vacuum, where Gab vanishes, $$ \left (\frac{1}{c^2}\frac{\partial^2}{\partial t^2} - \nabla^2\right ) \bar h_{ab}=0\;. $$
So this disturbance (gravitational wave) travels with the speed of light. Upon quantization, you can easily see that its quantum excitation, the graviton, is massless, and also travels with the speed of light, like all massless particles.
Note that the scale of gravity, Newton's constant G , or, equivalently, the Planck mass only enter in the coupling of this wave or particle to matter (and energy) and not in its free propagation in space, in this weak field regime, so it decouples here.
I'd like to add to Cosmos Zachos's Answer; but first, one can find a great deal more detail about the derivation of the wave equation for weak field gravitational waves as given in Cosmos's summary in Chapter 9 "Gravitational Radiation" of the book "A First Course in General Relativity" by Berhard Schutz.
Cosmos's answer is correct, but I'd like to point out that there is a sense wherein GTR is constructed from the outset to have a gravitational wave propagation speed of $c$, and one can also think of Maxwell's equations in the same way too. That is, their wave propagation speeds both equally derive from thoughts and postulates crafted in the special theory of relativity (or at least one can make this theoretical postulate and, so far, witness experimental results consistent with it).
The reason that the weak field analysis in Cosmos's answer / Schutz chapter 9 yields a D'Alembertian with a wave speed of $c$ is that, from the outset, General Relativity is postulated to be encoded as field equations constraining the Ricci tensor part (i.e. the volume variation encoding part) of the curvature tensor in a manifold that is locally Lorentzian. The "locally Lorentzian" bit is the clincher, here: to every observer there is a momentarily co-moving inertial frame wherein the metric at the observer's spacetime position is precisely $\mathrm{d} \tau^2 = c^2\,\mathrm{d} t^2 - \mathrm{d}x^2-\mathrm{d}y^2-\mathrm{d}z^2$ when we use an orthonormal basis for the tangent space at the point in Riemann normal co-ordinates. Of course, not every theory that takes place on a locally Lorentzian manifold has to yield a wave equation, but the weak field vacuum Einstein equations have a structure that does yield this equation, as in Cosmos's answer. The fact that the constant in that equation is $c$ hearkens right back to the local Lorentzian character of the scene (the manifold) of our theoretical description.
One can think of Maxwell's equations in exactly the same way, and there are several ways one can go about this. But once you postulate that Maxwell's equations are Lorentz covariant, then the constant in the wave equation that arises from them has to be $c$. One can begin with the Lorentz force law and postulate that the linear map $v^\mu \mapsto q\,F^\mu_\nu\,v^\nu$ that yields the four force from the four velocity of a charged particle acted on by the electromagnetic field $F$ is a mixed tensor. Now take Gauss's law for magnetism $\nabla\cdot B=0$ and postulate that it is true for all inertial observers. From this postulate, one derives $\mathrm{d} F=0$ if $F$ does indeed transform as a tensor. Do the same for Gauss's law for electricity $\nabla\cdot E=0$ in freespace and derive $\mathrm{d} \star F = 0$. From these two equations and Poincaré's lemma we get $\mathrm{d}\star \mathrm{d} A=0$, which contains D'Alembert's equation (with a one-form $A$ existing such that $\mathrm{d} A=F$, which is where Poincaré's lemma is deployed). And, from the Lorentz covariance postulated at the outset, the wavespeed in this D'Alembert equation has to be $c$.
So, in summary, the fact that the wavespeed is exactly the same for both theories arises because they have a common "source" theory, namely, special relativity as the beginning point whence they come.
The OP has probably already realized this, but, for the sake of other readers, there is really only one electromagnetic constant just as there is only one gravitational constant $G$; SI fixes $\mu_0=4\,\pi\times 10^{-7}{\rm H\,m^{-1}}$ and then the value of $\epsilon_0$ is wholly determined from the definition of the distance / time units through $\epsilon_0 = \frac{1}{\mu_0\,c^2}$. This one definition fixes all of our electromagnetic units; in particular, it fixes the definition of the coulomb. As in Cosmos's answer, $\epsilon_0$ doesn't come into the wave equation just as $G$ doesn't come into the gravitational wave D'Alembert equation and $\epsilon_0$ is only directly relevant when Maxwell's equations describe the coupling of the field vectors to charge.