It's lost at Boltzmann's "molecular chaos" or "Stosszahlansatz" step. If f(x1,x2) is the two-particle distribution function giving you (hand-wavingly) the probability that you have particles with position and velocity coordinates x1 and others with coordinates x2, then Boltzmann made the simplification that f(x1,x2) = f(x1) * f(x2), ie throwing away all the correlations between particles. This is where the time-asymmetry comes in: you're saying that after two particles collide, they retain no correlation or memory of what they were doing beforehand.
I assume (on the basis that it has not come up so far in this discussion and my limited further reading) that position-momentum uncertainty offers no justification for throwing away the correlations?
The systems we're talking about here are classical, not quantum, so the uncertainty principle isn't really relevant. I think the justification is mainly that it makes the analysis tractable. In physical terms it's simply not true that the interactions are uncorrelated, but you might hope that the correlations are "unimportant" in the long-term. In a really hot gas, for instance, everything is moving so fast in random directions that any correlations that start to arise will quickly get obliterated by chance.
I don't think it really helps - you're already working in something like a probabilistic formulation. If you want to use a quantum mechanical justification for it then you need to look at some sort of non-unitary evolution.
Besides that, I don't think anybody is really arguing that the correlations are actually lost after a collision, just that it's usually a good approximation to treat them as if they are.
