Decoupling capacitors are not really necessary when you power a linear regulator from a battery, and the cables going from regulator to battery are very small (a few centimeters).
However, it almost never hurts to have a decoupling capacitor and in some cases even a large input capacitor (especially in battery operated circuits) would help a lot.
In the video the guy used a 9v battery with short wires and the regulator outputs 5v so there's a large difference between input and output voltage.. it works.
You used an ac/dc transformer, unregulated, so I'm not even sure that you actually used a capacitor after rectification to smooth out the output of the bridge rectifier.. without a capacitor after the rectifier, you're going to have voltage going from 0 to some high voltage and back. The capacitor must be large enough to keep the voltage all the time above Vout + at least 2 volts
And even then a decoupling capacitor would be helpful.