Under which conditions do two moving bodies start orbiting each other around their center of mass?

Unless other objects are "near enough" to complicate the motion, the bodies can always be described by a two-body solution whenever both are in freefall (nothing is pushing one of them). The only difference that being close makes is that forces from other objects become less significant.

You could then describe their motion as one of two groups: a hyperbolic pass if speed is great enough ($\mathit{KE} + \mathit{GPE} > 0$), or an elliptical orbit ($\mathit{KE} + \mathit{GPE} < 0$). A collision can happen in either case, it just means the orbital paths intersect the surface of the objects.

Falling straight toward each other is just a degenerate case, where the ellipse minor axis (if a bound state) or the hyperbola transverse axis (if an unbound state) is zero length.

It depends on their initial velocity. If they start off not moving relative to each other, they will fall together and collide. But if they have a (sufficient, depending on their size) component of velocity perpendicular to the line between them they will orbit, or for a large enough component, fly apart.

Orbits are like a game of chicken.

Say you're walking down the street and there's someone straight towards you. If you both keep walking straight or don't make enough effort to side step, you'll end up colliding.

You don't want to collide, so you move to the side as you approach... if you're moving too fast you might side step too much, or walk too far at an angle, and then you end up flying off into the busy street or the field on the other side. That's probably going to hurt too.

So, if you manage to side step enough but not too much, you can miss colliding and walk around them. As you do, they get your attention and you slow down to talk... and end up stepping in behind them to not block people.

Orbits in classical mechanics are pretty much like that. For a two body situation:

• Two bodies lacking sufficient side ways velocity will collide.
• Two bodies with far too much side ways velocity will miss and only be deflected.
• Two bodies with sufficient but not excessive side ways velocity will continue to "miss" each other as gravity pulls their vector around the common center of gravity.
• So long as the two bodies don't attain escape velocity, the shape and size of the orbit of two given objects could be considered as derived from the variables of velocity decomposed to a scalar variable that in a radial direction and a vector variable in a tangential direction.

Hopefully I've got all that right, since I'm writing off the top of my head.