All that means is that if the capacitor is too small, it won't be large enough to damp the oscillations but if it's a single, large value capacitor it won't be good either. Higher value capacitors tend to have poor high frequency characteristics and become inductive past the resonant frequency, the higher the value, the lower the resonant frequency.
Rather than using a single, high value capacitor, it's better to use a large capacitor and lower value capacitor in parallel with one another. The type of capacitor is also important; for example tantalum is better than electrolytic. I'd recommend a 1uF tantalum in parallel with a 100nF and 10nF ceramic capacitor on both the input and output. If you don't have a 1uf tantalum, go with 22uF electrolytic.