What's the purpose of the two capacitors in parallel on each side of the regulator in
 this power supply circuit



I've seen similar setups in other similar circuits and can guess that it's related to one being polarized an one not, but I don't really understand what's going on there.

Summary:

Big capacitors handles low frequency ripple and mains noise and major output load changes.

Small capacitors handle noise and fast transients.



That circuit uses "overkill" with that application but serves as an OK example.
Here is a typical LM7805 datasheet
It can be seen on page 22 that having two capacitors at Vin abd two at Vout is not necessarily a standard arrangement, and that the capacitor values in the supplied circuit are relatively large.
Below is fig22 from the datasheet.

Your circuit:

A large capacitor like the 2200 uF act as a "reservoir" to store energy from the rough DC out of the bridge rectifier. The larger the capacitor the less ripple and the more constant the DC. When large current peaks are drawn the capacitor supplied surge energy helps the regulator not sag in output.
The white and black bars on the capacitor symbol show that it is a "polar " capacitor - it only works with + and - on the selected ends.
Such capacitors are usually "electrolytic capacitors". These have good ability to filter out low frequency ripple and to respond to reasonably fast load changes.
By itself it is not enough to do the whole job as it is not good at filtering higher frequency noise because electrolytics tend to have large internal inductance + large (relatively) internal series resistance (ESR).
The small input capacitor (here shown as u1 = 0.1 uF) will be non polarized and will usually nowadays be a multilayer ceramic capacitor with low ESR and low inductance giving it excellent high frequency response and noise filtering capabilities. By itself it is not enough to do the whole job as it cannot store enough energy to deal with the energy needed to filter out ripple changes and large load transients.
The same applies in general terms to the output capacitors.
C4 = 10 uF helps to supply any gross load changes thus taking some load off the regulator.  It is not usually deemed necessary to have more than a very small capacitor here. Some modern regulators need a largish capacitor here for stability reasons but the LM78xx does not.
Here the second output capacitor is 0.1 uF and it is there to deal with high frequency noise.
Note that having a large capacitor on the output can cause problems. If the input was shorted so that power was removed C4 would discharge back through the regulator.
Depending on voltage and capacitor size this can cause damage.
One method of dealing with this is to provide a usually reverse-biased diode from regulator output to regulator input. If the regulator input is shorted to ground the output capacitor will discharge through the now forward biased diode.

Added: Nils noted:

A very large reservoir capacitor may lead to increased noise. The on-time of the diodes would get shorter yet the same amount of power is transferred. This causes current spikes in the transformer which start to radiate out a noisy magnetic field. Bigger is not always better here. It's unlikely to cause problems in circuits that uses the 78xx series regulators though, they just don't move enough power usually.

Good point. Adding a small series resistor between transformer and 1st capacitor serves to "spread" the conduction angle, reduce current peak, reduce noise and make life easier for the diodes. Working out the diode current can be somewhat mind-taxing I seem to recall (having done it as an exercise long ago). Nowadays a simulation is easy enough to make calculation unusual.
