When an object bounces off of something, the bounce is not instantaneous, and in fact goes through a sequence of changes.
First, the object slows down to a stop, and both the object and the surface are deformed. If they are both hard, then the deformation will be very small, but it will still exist.
Second, both the object and the surface reverse their deformations, speeding the object back up in the reverse direction.
The difference that makes a softer surface produce lower bounces is that soft surfaces stop that second stage early, leaving the surface still partially deformed. This reduces the time of contact, and thus the impulse of the bounce. The energy lost to this is converted primarily to heat.
More spring-like surfaces also do it more gradually, leaving some of the un-deformation still in progress when the object loses contact with the surface. This reduces the force during the time of contact, and thus the impulse of the bounce. The energy lost to this is converted to more macro-scale vibration, which may even be readily visible.
Illustrating with an example:
A ball has 1000 kg * m/s momentum when it first touches a soft surface. The ball and surface each exert 100 N force on each other as long as they are in contact.
The first stage, the "impact", lasts 10 seconds. During the impact, the ball slows to a stop and deforms slightly, and the surface deforms a lot. Both the ball and surface cause an impulse of 1000 N * s on each other, during this stage by itself.
The second stage, the "rebound", lasts only 5 seconds. During the rebound, the ball accelerates away and un-deforms, and the surface un-deforms only partially. 621
Both the ball and surface cause an impulse of 500 N * s on each other, during this stage by itself.
The end result is that the ball bounces off with only half the speed it started with. For a hard surface in the same scenario, the rebound would instead last almost as long as the impact, about 10 seconds, the surface would un-deform all the way, and the ball would bounce with almost as much speed as it started with.
P.S. Notes on concepts and units:
Momentum: The product of mass and velocity. It has unit kilograms * meters / second, or kg * m/s. This unit is equivalent to N * s.
Force: How hard you're pushing on something. Its unit is Newtons, or N.
Impulse: The product of force and time, and also the change in momentum. It has unit Newtons * seconds, or N * s. This unit is equivalent to kg * m/s.
<PERSON>'s third law applies to force, and indirectly to impulse. It does not apply to momentum.
In typical everyday collisions, gravity applied over some previous time span may be the source of some of the momentum involved, but is inconsequential for the collision itself because it is utterly dwarfed by the forces exerted by the objects on each other. The collision between a ball and a hard floor takes something like a millisecond to finish, but produces an impulse large enough to reverse - not just stop - momentum that took around 500 milliseconds for gravity to build up. 621