Between the years 1687 and 1915, our best understanding of gravity was the one proposed by Sir Isaac Newton. It was Newton who formulated the famous Inverse Square Law, which says that the strength of the gravitational force between two objects is proportional to the mass of each of them, and also to the inverse of the square of the distance between them. Roughly: Gravity is stronger when objects are heavier, and when they’re closer to each other.
The force of gravity has both a strength and a direction. In our everyday lives, we feel a force pointing basically toward the center of the Earth. According to Newton, Earth’s gravity stretches far away, literally throughout the universe, though it grows weaker the further away you get. As the Earth moves, its gravitational field shifts along with it, instantly, everywhere in the universe; that instantaneous change is what gives Newtonian gravity its nonlocal character. Other stars and planets also contribute to the total gravitational force at any particular location in space, but in principle we could imagine isolating the Earth’s contribution.
We can even imagine sending signals this way. Everything causes gravity, so just waving a bowling ball back and forth causes changes in the gravitational force instantly throughout the cosmos. In practice it would be hard to pick out the force from one tiny object, but by thought-experiment standards it’s not that different from what real radios do with electromagnetic waves. A gravity detector far away could measure how we were waving our bowling ball, and we could use Morse code (or whatever) to send messages to it.
In a Newtonian world, those messages would travel instantly over infinitely far distances. Not only do they travel faster than light, they travel faster than anything.
Newton himself never liked this feature of his own theory. It wasn’t primarily the instantaneous speed of gravity, but the fact that the force seemed to propagate through empty space, rather than through a medium like the air. He found this “action at a distance” distasteful, but he left its ultimate solution “to the Consideration of my readers.”
These days we’re less hung up on the need for a “medium” through which forces propagate. Spacetime itself is good enough for modern physics. We say that spacetime is suffused with different kinds of fields—including electromagnetic fields and the gravitational field—and disturbances in them can propagate even through empty space. That’s what electromagnetic waves are (light, X-rays, microwaves, radio waves), as well as the newly-discovered gravitational waves.
To modern physicists, it’s the “instantaneous” part of Newton’s theory that causes discomfort, not the lack of a medium for gravity to travel through. Would you want to live in a world where technologically advanced aliens in the Andromeda galaxy could—in principle—eavesdrop on what you were saying right now?