How critical are the input and out capacitor values in a linear voltage regulator?
The input capacitance value is not critical.  What is critical is that you have some way of preventing the input voltage from dipping during operation over a wide frequency band.

The connection between the power source(battery, generator, AC power, etc) and the regulator input will have some inductance L.  In a linear regulator current passes from the input of the regulator, goes through a pass element (usually a BJT, MOSFET, or IGBT), and then flows to the load.  The input and output current are typically about equal except for a small amount of extra input current used to run the regulator internal circuitry (reference, error amp, gate drive).

Suppose that the regulator input current increases at a rate of di/dt (due to the load current changing).  Then without any input capacitance the input voltage to the regulator would dip by an amount V_dip = L * di/dt.  Clearly if the voltage dips too much then the regulator will stop working and the output load voltage would drop.

The datasheet will usually recommend a minimum required capacitance on the input, but you can always use more.  Ceramic capacitors tend to work well over a wide frequency band but have lower capacitance values.  Electrolytic capacitors have larger values but work only at lower frequencies.  Typically a combination of both types is used to get both high capacitance and wide frequency operation.

Linear regulators typically have an error amplifier and pass transistor inside of them.  Both of those components have limited bandwidth.  If the output current changes too rapidly then the regulator will not be able to adjust to the demand changes quickly enough and the output voltage may dip.

The amount of output dip at frequencies much higher than the regulator bandwidth is approximately dV = I/(2 * pi * f * C).  For example if you had a regulator with a bandwidth of 100kHz, and you were running some digital electronics that drew 100mA spikes at 1MHz and had a 0.1uF output capacitor then the output ripple would be 100mA/(2*pi*1MHz * 0.1uF) = 15.9mV peak.

Typically you would try to pick a capacitance that leads to an acceptable ripple voltage (using the above equation) at the peak load current at the frequency corresponding to the regulators bandwidth given in the datasheet.

Another factor to consider for the output capacitor is stability.  The error amplifier in a linear regulator typically uses feedback and can oscillate if too much or too little capacitance is used.  Many linear regulators are stable with a wide range of output capacitances.  The datasheet will often specify that the capacitance must be below or above a certain value for stable operation.  

You cant really calculate how much capacitance is required for stability without knowing the characteristics of the error amplifier (phase and gain margin vs. frequency).  Since the manufacturer often doesn't tell you that information you sort of have to take the manufacturer at their word on that one.