How does general relativity eliminate the Newtonian action at a distance? By the mediation of which "carriers"? I found in Wikipedia the following statement 

From a Newtonian perspective, action at a distance can be regarded as: "a phenomenon in which a change in intrinsic properties of one system induces a change in the intrinsic properties of a distant system, independently of the influence of any other systems on the distant system, and without there being a process that carries this influence contiguously in space and time.

Later on, I see at the same site,

This problem has been resolved by Einstein's theory of general relativity in which gravitational interaction is mediated by deformation of space-time geometry. Matter warps the geometry of space-time and these effects are, as with electric and magnetic fields, propagated at the speed of light.

I am not good at general relativity so I am asking the following: since celestial objects are in permanent movement, do they permanently emit gravitational waves? If so, they should lose energy permanently. Shouldn't this loss affect their trajectory? Or, alternatively, is it a negligible loss comparing with the loss by other types of radiation (e.m. radiation, particle radiation, etc.)?
A practical example: imagine that an object comes from afar, e.g. an asteroid approaching the Earth. As long as it travels through "empty space*, it is not accelerated (at least, not by the Earth). But, getting closer to Earth there is a moment, or a time-interval, when the asteroid begins to feel the Earth's presence, and begins to accelerate. How so?. I understand (if I understand correctly at all) that during body's non-accelerated movement, there is no radiation exchanged between it and the Earth. Then how does the asteroid begin to feel the Earth's presence? By the mediation of which carriers?
 A: The massive body that is moving changes the gravitational field (or the metric) around it. This change happens at the speed of light and the delay can be (and was experimentally) detected. The carriers of the information of this change are believed to be gravitons (some particles that nobody detected so far, although there are various reasons to believe on their existence). The propagation of graviton can be considered (like in the case of photon) a gravitational wave (or electromagnetic wave in case of photon).
The emission of gravitational wave does take energy. In some rapid and very very massive systems this can lead to substantial loss of energy. The obvious example to check was a binary neutron star system. Russell A. Hulse and Joseph H. Taylor, Jr measured it first on a newly discovered type of a pulsar (neutron stars) and got themselves a Nobel prize 1993. This was also an indirect confirmation of the existence of gravitational waves (the direct measurement has not$^{*}$ been done yet, although there are several GW detectors around the world).
$^*$Update: Gravitational waves have been directly detected, cf. https://en.wikipedia.org/wiki/List_of_gravitational_wave_observations
A: Gravitational waves are emitted by oscillating quadrupoles (and higher moments). Compare this to electromagnetism where EM radiation is emitted by oscillating dipoles.
So an isolated body travelling along in space will not emit gravitational waves and won't lose energy. I can't offhand think of any physically plausible oscillating gravitational dipoles, but they wouldn't lose energy either.
As Robin says in a comment, the obvious example of an oscillating gravitational quadrupole is two masses in orbit around each other. These do radiate energy, and indeed this has been measured for binary neutron stars. However even in such an extreme system the amount of energy radiated is small. It's measurable only because we have two very compact, very massive objects orbiting each other with high angular frequency. For normal cosmological objects like binary stars, solar systems, galaxies etc, the rate of gravitational wave emission is so low as to be completely negligable.
A: I'm not a PhD in physics either or even a physicist for that matter, however, it's my understanding that all moving bodies in space will lose kinetic energy continuously over time.
For example, let's say the universe consists of a vast vacuum and one moving planetary body. That body will continually lose kinetic energy over time. Why? I'm not sure. Perhaps virtual particles would have something to do with it.
According to cosmological theory, the universe will eventually suffer heat death. There will be no motion except perhaps atomic motion. Again, I'm not a physicist.
http://www.newscientist.com/article/mg20927994.100-vacuum-has-friction-after-all.html#.VL6G7mwo6Cg
