One might ask the same question in a simpler example, like rotations, as MaxwellsDemon suggested. Or we could even ask why translations commute. I do like the observation that you can just go and look and see that rotations don't commute while translations do. Still, I think we can ask for additional physical insight into the problem.
The simplest case has got to be translations. Experimentally, translations commute (you can check by walking in squares in a parking lot, though you might get you some strange looks). However, they don't have to commute. If you try walking in big squares on a hilly lawn, you'll find that translations don't commute. I think it's reasonable to say that this is physically because the ground is now curved. Another way to say it is that in some sense the action of translation depends non-trivially on where you start (when there is curvature).
The same kind of reasoning works for boosts. In Galilean relativity boosts are just like translations. In particular, the space of velocities looks just like R^3 and there is no curvature. What happens in special relativity? Now velocities are limited to be less than or equal to one in magnitude (in units with c = 1). The space of velocities looks like a ball in R^3. But this is no ordinary ball, because the boundary of the ball is infinitely far away in a precise sense. For example, it takes an infinite number of small boosts to reach the speed of light. This idea can be translated into a precise notion of a metric on the space of velocities. This metric makes the space of velocities into a curved hyperbolic space. Thus from the physical insight that there is a maximum speed, we should not be surprised that boosts don't commute.
You can also make precise the idea that boosting depends on where you start in a non-trivial way, but I don't have time to elaborate right now.