Why is there always a capacitor on input and output of a voltage regulator?
Most voltage regulators (especially LDO types) require a capacitor on the output for stability, and it will usually improve transient response even for regulators like the 7800 that may not strictly require it. An input capacitor is usually required to reduce source impedance. 

It is impractical to make capacitors more than tens of pF (or so) on an inexpensive chip- they take up too much expensive silicon area, and external ceramic or electrolytic capacitors are very cheap in quantity. That is not in the cards. And the capacitors actually provide energy storage so it's not something that clever circuitry can substitute for. 

The values are compromises that make sense based on the chip stability behavior at different load currents, and also what caps were common when the datasheet was composed (that might be 35 or 40 years ago for the 7800 series). It is almost always acceptable to use a larger capacitance on the input, and usually acceptable on the output, however there may be minimum/maximum values on the capacitor ESR- the equivalent series resistance. In some cases a capacitor that is too ideal may cause the regulator to oscillate. 

Most modern regulators will indicate what values and types of capacitor are acceptable, so reading and understanding the datasheet is all you need to do.