When you rectify an AC voltage to a DC voltage using 4 diodes, you get a DC voltage that has a peak dc voltage equal to :
Vdc peak = sqrt(2) x Vac - 2 x (voltage drop on one diode of bridge rectifier)
and the maximum DC current can be estimated with formula :
Idc max = 0.62 x Iac (where 0.62 is a constant that works fairly well for small transformers)
So let's say your AC transformer/adapter outputs 9v AC 9VA (this means Iac = 9VA / 9v = 1A)
Your peak DC voltage will be Vdc peak = sqrt(2) x Iac - 2 x 0.8v = ~ 11v
and the maximum AC current of the example AC transformer/ adapter would be 0.62 x 1A = 0.62 A
However, it's important to keep in mind that small transformers will often output a higher AC voltage at idle, 10-15% above at idle/low load would be normal, so without any load the AC output of the adapter could be 10v AC which means after rectification you could have more than 11-12v DC peaks.
This is important to remember when choosing the capacitor that smooths the DC voltage after the bridge rectifier - in this case the 11-12v is low enough that you can use 16v rated capacitors, but had the AC voltage was 12v, then you would have to use 25v rated capacitors.
A linear regulator produces the desired output voltage as long as the input voltage is higher than the output voltage plus the dropout voltage. In the case of 7805 linear regulators, this dropout voltage is around 1v to 1.5v (it varies with temperature and the output current)... for safety, let's just go with 1.5v
So you would want the input voltage of your 7805 linear regulator to always be at least 5v+1.5v = 6.5v. For extra safety let's plan to have at least 7v all the time.
You can estimate how much capacitance to have after the bridge rectifier using this formula :
Capacitance (in Farads) = Maximum DC current / [ 2 x Mains AC Frequency x (Vdc peak - Vdc min desired) ]
You say your Arduino is going to consume at most 100mA (0.1A).
Let's plan for the worst case scenario where the mains voltage is low and your peak DC voltage after rectification is only 10.5v and let's say you want a minimum of 7v at 0.1A ... so put the numbers in formula :
C = 0.1A / [ 2 x 60 Hz x (10.5v - 7v) ] = 0.1 / 120 x 3.5 = 0.1 / 420 = 2.381e-4 Farads or 238uF (
https://www.wolframalpha.com/input?i=2.381e-4+farads+to+uF )
So anything higher than 238uF will only increase the minimum DC voltage above 7v, if the regulator outputs 5v at 100mA. At lower current, the minimum DC voltage will be higher than 7v.
You can use bigger capacitors, like 470uF or 820uF or 1000uF, but it won't make a difference in your circuit, because the linear regulator will not care that your input is 8v or 7v, the regulators simply "throws" away the excess in the form of heat.
In this example, for maximum 100mA output current, I'd probably go with a 470uF 25v rated capacitor, simply because they're very common value+voltage combination.
Note that there are linear regulators out there which have a much lower dropout voltage of let's say 0.3 - 0.6v, so with those you could have a lower minimum input voltage.
A 100nF or 1uF ceramic capacitor as close as possible to the input voltage of the regulator is recommended ... it's for decoupling, filtering high frequency stuff that an electrolytic capacitor is not optimal for.
As for the output capacitors, linear regulators like 7805 don't require a lot of capacitance, so I would say you'd be fine with 10uF to 100uF on the output. The output voltage is 5v, so you'd be fine in theory with a 10v rated capacitor, but most people don't stock capacitors with such low voltage rating and generally there's little benefits to stocking them (for example the diameter and height are often the same as 16-25v rated versions).
I'd use a 10uF-47uF 25-35v rated electrolytic.
The linear regulators throw out the difference between input and output as heat. So the amount of power the regulator will dissipate is P = (input voltage - output voltage ) x current.
In your case, assuming an ideal case where your input voltage is always the maximum possible of 11v and it outputs 5v at 0.1A then the regulator will produce
P = (11v - 5v ) x 0.1 = 6 x 0.1 = 0.6 watts
A typical to-220 package will have a thermal resistance of around 20-24 c/w ABOVE ambient ( see for example page 4, 23.9c/w for this to-220 version here :
https://www.ti.com/lit/ds/symlink/lm340.pdf )
That means at 0.6 watts, the linear regulator will probably be around 15 degrees Celsius above ambient. The regulator will function properly even at 125 degrees Celsius, but in general it's a good idea to keep it below 100 degrees Celsius.
In practice remember the input voltage is not gonna be that ideal 11v, it's going to be between 7v and 11v depending on how much your arduino consumes and how big your capacitors are