Death of Zen (Audio Amplifier) Questions
For all of the capacitors, what should the voltage rating be?

There are no really big capacitors in the circuit, so don't worry too much about price difference. 35V voltage rating is too low, you don't want your components used at their maximum. I believe the next commonly available voltage is 63V, but I guess you can use anything above 40V.

Is the polypropylene required?

No the polypropylene is not required. It is probably used because it has better performance for higher frequencies. Electrolytic capacitors have a relatively high parasitic series induction and by connecting a smaller polypropylene cap in parallel you get best of both worlds. The electrolytic capacitor is big and cheap, the polypropylene has better specs for higher frequencies but is relatively expensive. 

through a bridge rectifier

If you are sure that the voltage is not exceeding the 35V, why don't you try it? You're going to hear a hum from the mains, 100 or 120Hz, depending on where you live. It is a great way to learn. Sometimes a voltage regulator fails and you'll recognize the sound and know immediately what a problem with an amp is.

Best though is to get a series regulator to stabilize the power supply. Now this can be a bit tricky because:


power supply ripple: On your oscilloscope, check the lowest voltage from your power supply under maximum load. You'll recognize the 100/120Hz ripple, you want the minimum voltage to ground.
drop out voltage: A series regulator requires a minimum voltage across in- and output of the regulator. If you use an integrated regulator, check the datasheet for this parameter. You'll have to subtract this value from the value found under 1.
maximum current: Check the datasheet of the regulator if it can supply the maximum current that you need
cooling: Calculate how much power is dissipated in the series regulator and use a proper sink to keep. Good practice is to keep sink temperature below 70 or 80 degrees Celsius. But you'll have to carefully calculate how large the heatsink for the regulators (and the output power transistors!) need to be. That is worth a question on its own though. ( https://www.youtube.com/watch?v=8ruFVmxf0zs )


EDIT: What should the value of C3 be?

I missed the capacitor sizing question and I initially understood the mentioned parallel caps were a given. I personally think 4Hz (as @Andy calculates) lower cut off is really, really low. 20Hz is already pretty low for a audio project like this. I'd personally calculate with 4 ohm for the speaker impedance though.  With these numbers C3 could easily be halved to 2200uF. @Andy's formula is easy enough to experiment with the values you have lying around. Cost and physical size are the important factors here. Also as mentioned before, I agree with @rawbrawb that the parallel polypropylene is a bit overdone for a project like this, but hey, if cost of the cap is not an issue it is nice to experiment with and form an opinion of your own.