You can use the equations of GR (General Relativity) to set up the problem of a mass moving (either with or without a constant velocity) in an otherwise uniform space-time and we see that the gravitational effect on another mass travels at the speed of light. (Essentially the key here is that distortions in space-time travel at the speed of light, since the distortions themselves only transmit energy. They don't have any mass-energy of their own.)
As to the wave nature of gravitation, I believe that Einstein had no (firm) reason for saying this. One of his main motivations in developing GR was an analogy with Maxwell's equations for electro-magnetism, which (at the time) was by most considered to be a wave phenomenon. Now, Einstein himself helped contribute to the theory of the particle nature of light. So there still existed the possibility that gravity might take the form of a particle as well. If it did, since the influence of gravity travels at the speed of light, the graviton would be massless. In this case GR predicts that the graviton has a spin of 2, rather than the spin 1 case for the photon.
As to how such waves work, they are almost identical in properties to light waves. They are transverse waves, have a wavelength, etc. The difference is that such waves couple to every kind of particle, whereas light waves only couple to charged particles. (Graviational waves also cause time distortion, which is a whole other barrel of apples and I don't know enough about this to even speak of it, really.)