The datasheet states:
This capacitor need not be an expensive low ESR type: aluminum electrolytics are adequate. In fact, extremely low ESR capacitors may contribute to instability. Tantalum capacitors are recommended for systems where fast load transient response is important.
Where the regulator is powered from a source with high AC impedance, a 0.1 μF capacitor connected between Input and GND is recommended. This capacitor should have good characteristics to above 250 kHz.
The voltage rating of the capacitors depend the maximum possible (peak) voltage they can encounter. Pick a voltage rating 1.25 times (elco) to 2 times (tantalum) the highest (peak) voltage the capacitor will see.
I'd go for safe if price and/or size don't matter, so, e.g. a 50V rating for the output.