The transformer definitely comes before the rectifiers. Simplest to implement would be a regulated supply based on a 7805 voltage regulator. Here's a good basic circuit. Not sure how much current is needed but a 2-amp transformer is overkill for a microcontroller that's just reading sensors. I'd look for one that's rated somewhere between 300mA and 1A. Any diodes in the 1N400x series would be OK; bridge rectifiers with all four in one package are also available. The secondary voltage on the transformer could be between 6 and 9 volts.
EDIT: Opps, forgot what we were doing here. The above circuit is fine, and its output can be fed directly to the 5V pin on the Arduino. But, the Arduino has its own voltage regulator on board, so that could be eliminated from the above circuit and the output of the rectifier (pin 1 on the regulator) can be fed directly to the Arduino's Vin pin, or to the power jack (the two are connected). C3 of course is also eliminated along with the regulator. I might keep C2, but I'd use 0.1µF instead of 0.01µF. If I were building the entire circuit, I'd use 0.1µF for both C2 and C3.