Newton said the speed of gravity is infinite but according to Einstein (and some nifty interstellar measurements), it most certainly is not.
But in general relativity, things are much more intricate, and incredibly interesting. First off, it isn't mass, per se, that causes gravity. Rather, all forms of energy (including mass) affect the curvature of space. So for the Sun and the Earth, the incredibly large mass of the Sun dominates the curvature of space, and the Earth travels in an orbit along that curved space.
If you simply took the Sun away, space would go back to being flat, but it wouldn't do so right away at every point. In fact, just like the surface of a pond when you drop something into it, it snaps back to being flat, and the disturbances send ripples outward!
