How does Einstein's Theory of Relativity predict the existence of Gravitational waves?
Relativity requires that nothing can travel faster than the speed of light. This includes matter and even other effects like electric fields, gravity, etc.
Relativity requires that no effect can travel faster than the speed of light. A change doesn't affect all points in space instantaneously. Instead, the change must ripple out from the source to reach other points in space. Therefore, any periodic changes in gravitation will propagate outward like a wave travelling at the speed of light.
The existence of these waves was predicted by Einstein in 1916. However, it requires a very large event with large masses and high accelerations, and very sensitive equipment to detect these waves.
Today, Feb. 11, 2016, it was announced that the LIGO team successfully measured gravity waves emanating from the coalescence of two orbiting black holes into one! LIGO Collaboration website