A moon-sized object is running loose in the Solar System, perhaps after a planetary collision. As it approaches a planet, it's presumably following an approximately hyperbolic path. If it goes on past, it's still on the same hyperbola, on a curve mirroring its approach (presumably). How can the planet ever capture it, whatever the body's velocity? Why doesn't it either collide or go on past?
How can a planet capture a moon?
There are 178 moons in the Solar System, according to the NASA Planetary Fact Sheet, so it seems to be a common event. The following sections will show that moon capture is actually unlikely, but when a planet has one or more moons capture becomes easier.
Starting from the initial conditions, the planet is in orbit about the sun, and an asteroid is in a different orbit about the sun.
In order for capture to become possible, the asteroid and the planet must come into proximity. When the asteroid comes inside the Sphere of influence of the planet, the gravity of the planet is the main factor in determining the path of the asteroid.
Relative to the planet, the asteroid will be following a hyperbolic trajectory, and hence has sufficient kinetic energy to avoid capture. A large variety of outcomes may occur, but the ones that lead to capture are those where the asteroid somehow loses enough kinetic energy for its velocity to fall below the escape velocity of the planet while retaining enough energy to achieve a closed (elliptical) orbit. The main (not the only) possible outcomes are
the orbit of the asteroid is perturbed, by a greater or lesser extent, and it continues on its way out of the sphere of influence of the planet.
the orbit of the asteroid is perturbed, and the asteroid impacts the planet surface. That would usually be the end of the process, but current theories on how Earth captured the Moon are that a body named Thea impacted the Earth, and the Moon formed from some of the collision debris.
the orbit of the asteroid is perturbed, and the path of the asteroid intersects the atmosphere of the planet, losing kinetic energy as heat in the atmosphere (similar to aerobraking).
the orbit of the asteroid nears an existing moon of the planet and is accelerated (in the sense that deceleration is just acceleration with the opposite sign) by the existing moon, as used by the MESSENGER spacecraft to slow its speed before orbiting Mercury.
The last two cases admit the possibility of capture.
After losing energy in the planetary atmosphere, if the asteroid has lost enough energy it may enter a closed orbit around the planet. The problem is that the orbit will intersect the atmosphere again, losing energy each time it does so, until it impacts on the planetary surface. Capture can occur when an existing moon is present and is in just the right place for its gravity to reduce the eccentricity of the orbit of the asteroid.
So, the most likely case where a planet can capture a free asteroid is when there is already one or more moons present. The incoming asteroid must avoid entering the Hill sphere of the existing moon - the region where the moon would dominate the path of the asteroid.
Gravity assist can accelerate an asteroid when the asteroid is passing outside the orbit of the moon, but can decelerate the asteroid is passing inside the orbit of the moon. In this case some of the kinetic energy of the asteroid is transferred to the moon. As is the case with aerobraking capture, gravity assisted capture requires the existing moon to be in just the right place.
A rather elegant paper published in Nature (mentioned below) shows how two bodies orbiting each other as they approach the planet could have led to one being captured by Neptune. This mechanism could apply in other cases also. This Dissertation (pdf) discusses a similar process for Jupiter.
It turns out that irregular shaped bodies can be captured more easily than spherical bodies. Orbiting within the Hill sphere of the planet is not enough for capture to be permanent. Only orbits in the lower half of the Hill sphere are stable. Bodies in higher orbits can be perturbed by nearby planets, and the body can eventually be ejected. But irregular shaped bodies exert minute fluctuations in gravitational attraction on the planet, and actually orbit in a chaotic manor. When other moons or rings are present these chaotic orbits gradually transfer energy to the bodies in the lower orbits, causing the new body to orbit lower, and hence become immune to external perturbation. 
Prograde vs retrograde orbits
The same analysis of chaotic orbits, and earlier work also concluded that retrograde orbits are more stable than prograde orbits. Whereas prograde orbits are only stable in the inner half of the Hill sphere, retrograde orbits can be stable out to 100% of the Hill radius. Hence retrograde capture is more commonly observed (this is not the whole story, it is still a matter if research).
Multiple existing moons, rings, and the early Solar System
While the probability of a single moon being in the right place at the right time is low, when there are multiple moons the probability of an initial helpful interaction rises linearly. But the probability of additional interactions rises geometrically, so the more moons a planet has the more likely it is to capture more. The existence of rings also aids capture by exerting a drag on the new moon, taking it's energy and lowering it's orbit, in much the same way that uncaptured gas would do in the early Solar System.
The biggest planets have the most moons
It may be obvious, but the biggest planets have the most moons. This is because they have deeper gravity wells, and sweep in more objects. Even though the probability of capture is low (most objects are just pulled into the planet), a steady trickle have have captured over millions of orbits.
Each capture mechanism requires a fortuitous set of conditions, and so is actually a quite rare event. One mechanism is a that a pair of co-orbiting asteroids become separated when one enters the planetary Hill sphere. The odds for an individual asteroid are improved when the asteroid arrives with low kinetic energy that must be given up to other bodies orbiting the planet, and when there are already many moons or a ring system.
There are two effects that alter the simple hyperbolic (or elliptic) relative orbit of any minor body ("moon") and a planet.
First, the gravity of the Sun (and to a much lesser degree of Jupiter). To good approximation the planet-Sun system is a circular binary and the moon a test particle (its mass negligible). The orbits of test particles in such a system (known as the restricted three-body problem) are complicated, but the Jacobi energy, preventing capture (similar to the angular-momentum conservation for the hyperbolic orbit). Hence, capture requires deviation from this approximation, in particular the moon's mass must not be too small and/or another interacting body participates (the Wikipedia page on asteroid capture is quite disappointing).
Second, tidal forces can transfer orbital energy into internal energy (of the planet and/or moon), which is then dissipated (converted into heat). Under lucky circumstances this process can be sufficient to convert an unbound to a bound orbit. Once bound, tides will continue to bind the moon more and more.