Well the capacitance at the output node contributes a pole to the regulators transfer function (why? because the common emitter output stage of a LDO has high dynamic output resistance, in contrast to an emitter follower - if the output resistance is very low the capacitance's phase shift is neglibile). Now here's the catch: the ESR plus the capacitance also do something, they give you a zero (which gives positive phase shift, increasing stability). If C and C_esr are controlled, the zero and the pole will about compensate, and the regulator is stable. (Also see National/TI AN-1148)
So the issue is, that such a simple regulator is usually not stable with loads that have high capacitance or low ESR (e.g. ceramic caps).