If you use switching regulators then the simplest solution is a single secondary winding producing 12VAC or more, rectified and filtered to produce >15VDC and powering both regulators in parallel. However designing and building those switching regulators may not be as simple as you would like.
3 terminal linear regulators are easier to implement, but for efficiency you need to avoid large input-output voltage differences. Powering the 5V regulator from 15V would be extremely wasteful, and running it in series with the output of the 12V regulator is not much better (plus it would increase the current load on the 12V regulator).
The solution is to feed the 5V regulator from a lower voltage. Normally this would require an additional transformer winding, rectifier and filter capacitor. However you can get full-wave rectified low and high voltages from a center tapped transformer and a single bridge rectifier, and then only one extra capacitor is required.
The trick to getting good linear regulator efficiency (and a cool running power supply) is to maintain a low voltage differential. The transformer, rectifier, smoothing capacitor and regulator are all 'overrated' to reduce their voltage drop under heavy load. That way the voltage differential can be kept low without risking output glitches due to ripple.
Here is the circuit I use to power external disk drives and small computers that may need up to 1.5A at +5V and +12V. Diodes D1~D4 are actually a 25A bridge rectifier...
NOTE: C1 really should be rated for at least 25V for safety, as 16V is right on the limit.