For all intents and purposes gravity travels at the speed of light but it is very hard to measure, and so far we have no direct model-independent measurement of the speed of gravity. Physics has to main gravitational models: Newtonian dynamics and General Relativity
The Newtonian gravitational model assumes that the gravitational interaction is instantaneous, and we know that this is wrong for several reasons: an instantaneous force points directly at the present position of the object upon which it is exerted. If this was the case in our solar system every single orbit would be unstable.
In general relativity gravity is expected to propagate at the speed of light. This can be tested by observing decaying binary star systems. These systems (like for example the pulsars PSR 1913+16 and PSR B1534+12) are gradually getting closer together and the decay is attributed to the loss of energy due to escaping gravitational radiation. According to general field theory radiation has a finite velocity and, if general relativity and its underlining principles are accepted, this velocity can be computed. The actual measurement confirms that the speed of gravity is equal to the speed of light to within 1%.
Is there a way to measure the speed of gravity independently of our models? This lies in our future ability to detect gravitational waves. We have few missions in preparation (http://sci.esa.int/lisa/) and several ground based laboratory looking for gravitational waves. If we can detect a wave connected with a visible event (supernova, neutron star collision, etc.) then we could be able to test the speed of gravity without having to rely on Einstein’s relativity.