First Starting?
Build it with either; it will work fine for you. The second option with the large capacitors and the extra small one is "more stable." Just build this, do not worry about why if you are just wanting to start your project. Let us know if something does not work.
100nF
Use the values that are suggested in the datasheet. If you add capacitors a factor of 10 smaller (called decade capacitors) it will help with higher frequency noise (RF, or radio band noise), as an effects of the impedance of a capacitor.
Feel free to add as many decade capacitors as you want, but you will not need them unless you start having FCC testing. They cannot hurt.
100uF
When someone increases this they are allowing their circuit to pull power from the power source for longer. If you have a long power line this will act as a small tank of power. If you are going to have long power lines, or very inductive power lines, add this.
The 7805 will drop out typically around 1.6V above the output voltage. At 1A it's guaranteed to not drop out with 2V of input-output differential. Most likely you'll not be running anywhere near 1A or you'd be using a switching regulator, but even at low current the dropout is not so low- that's because the 7805 is not an LDO regulator and there are Vbe drops in there.
One could guess that the input ripple rejection probably deteriorates as you get close to the dropout voltage and the gain drops. The datasheet specification is at 5V input-output differential, so they sidestep that issue. If you have a sensitive analog circuit like an RF module you may wish to use a higher input voltage than the absolute minimum.
If you're using a 7805 with unregulated (transformer, rectifier and filter) input voltage probably needs to be something like 10V to be safe and account for line voltage tolerance, ripple and so on). If you're using it with a regulated supply (like a switching wall wart) 9V is good, 7.5V is okay, but 6V is not high enough. There are LDO regulators that have very low dropout (so 6V would be fine) but they have other disadvantages (they are only conditionally stable- pay careful attention to the output capacitor value, ESR and type), they are more expensive, less sources, and generally have much lower input voltage capability so they're easier to fry with input transients. Much modern electronics uses LDO regulators and/or switching regulators, there are literally thousands of possible parts to use, but none yet has quite the staying power of the 7805/78M05/78L05.
I would say that if you need a heat sink on the 7805 it's time to move to a switching regulator in most cases. There's no problem using the 7805 or 78M05 at 10, 50 or 100mA, and it's better than a 78L05 (more expensive, but the circuit is different and has better guaranteed performance). The trade-off of an LDO vs. a 78xx regulator is a bit more complex and it is heavily dependent on the input voltage and how much control you have over it.
Best Answer
Such output caps are for Smoothing for very quick current droops. and ceramic caps for even much faster current noise in the regulation line such as if the sensing element is not to be perturbed by linearity loss