Most 7805 datasheets specify an input capacitor of 0.33uF or so. This one (the LM340 http://www.ti.com/lit/ds/symlink/lm340-n.pdf) at least specifies that the cap is only required if the regulator is "far" from the power supply filter, without further qualifying what "far" means. 0.33uF is nowhere near low impedance at power line ripple frequencies so we can rule that out.
Edit: the differences are self evident in the title of the question.
The input capacitor reduces the impedance of the power feed as seen by the regulator. This reduces input voltage fluctuations that occur as a function of current demand fluctuations, which the regulator has no control over. The regulator can do a better job of keeping the output steady when the input is steady.
The regulator electronics are specifically designed to keep the output steady with the input varying over a wide range (that's the point of a linear regulator), but no such circuit is perfect. Note the input regulation spec in the datasheet. That tells you how much input variations are attenuated to the output. However, that is usually at DC. As the frequency of input variations goes up, the active circuit becomes less effective at attenuating them to the output.
Fortunately, a capacitor has lower impedance at higher frequencies, thereby reducing the voltage fluctuations due to current fluctuations at higher frequencies. The capacitor does a better job as the active circuit does a worse job. Another way to think about this is that the capacitor together with whatever impedance there is in the power feed to the regulator form a low pass filter. This filter reduces the high frequency voltage fluctuations that the active circuit is less good at dealing with.
Remember that a pcb trace or wire has parasitic resistance and inductance, these effects need to be taken into account if the regulator is farther away from the supply. These effects can be calculated with the RCL filter equations and by estimating or measuring the inductance and resistance of the wire between the supply and regulator. The source impedance is being reduced by the inductance of the wire. This is 'propped up' by placing capacitance near the 7805. Since engineers are generally lazy, we don't do this because it is much easier to put a capacitor value that is sufficiently large.
If this problem is really keeping you up and night and a few cents is going to matter in your design, then either run through the calcs and find a model for your circuit or experimentally verify it. I suppose for academics sake's you could delve into the inner workings of the 7805. A frequency model, however, could be found and you could analytically determine if it would make a difference. Which would be a colossal waste of time. A better way would be to experimentally verify it. Put the cap on, measure the AC noise across the resistor with a meter or scope. Change the value, measure again, find out which is better.
simulate this circuit – Schematic created using CircuitLab
A voltage regulator is essentially a combination of a voltage reference with an amplifier. Your schematic shows a fairly complex multi-stage amplifier.
The trouble with multi-stage amplifiers is you can get positive feedback through the power supply. It is extremely difficult to make a multi-stage ampflier stable if it's power supply can act as a feedback path. Therefore the incoming power needs to have a low impedance across a wide frequency range.
At the low end of the frequency range the low impedance is provided by the power supply feeding the regulator but at high frequencies the wires (or PCB traces) feeding the regulator have significant inductance and so a local capacitor is needed to maintain a low impedance.
The data sheet mentioned that "Bypass capacitors are recommended for optimum stability". There is a possibility that the regulator be un-stable and self oscillating. 'Far (long) connection wiring' added inductance and reduce effectiveness.
Many decades ago, when 3 pin regulator first came out, I recalled manufacturers spending more words in data sheet to explain this. Now, it seems more relax. May be the part are 'more stable' nowadays? To be on the safe side, use a low ESR capacitor as data sheet recommends.
http://electronicdesign.com/boards/don-t-bypass-your-capacitor
http://forum.arduino.cc/index.php?topic=116916.0
http://www.eevblog.com/forum/projects/unstable-linear-voltage-regulator/
The input voltage supplies the whole regulator. If the input voltage has some high frequency components then the circuit can't operate properly because power supply rejection gets worse for higher frequencies.
Using a capacitor on the input side will limit the noise to low frequencies where the circuit can handle it.
Since the circuit contains nonlinear elements (transistors) noise on the supply can create DC shifts in the circuit, in this case the capacitor on the output does not help.
If your supply is clean, the capacitor shouldn't be required.
Another thing is transient response in case of load variations. The current consumption of the regulator depends on line/load conditions. If the supply is too far away, the line inductance will limit the ability to vary the supply current quickly. The transient performance suffers.
