Blinking the LED on/off to control its brightness with a PWM is definitely not the only way to control output. And if you are controlling by blinking, PWM is still the bottom of the pile in ways to blink, from a quality of light point of view.
I guess that because LEDs are actually so efficient, that isn't such a bad idea as it sounds at first.
The former approach might negatively affect the efficiency, though, depending on where the efficiency peak is.
How wrong am I to think that a capacitor after the PWM-regulator would give a reasonably good approximation of a constant voltage?
A capacitor on PWM output will give a decent approximation, _if_ it is big enough. For large LEDs this can be very costly (relative to other parts in system). Though the inductor in a switching converter is also a big cost driver.
Both for the capacitor, inductor and wrt to human perception increasing switching frequency helps. So that is what modern designs focus on normally.
A challenging aspect of LEDs is their nonlinear voltage versus current characteristic. A small change in voltage gives a very large change in current, and thus in output power. The characteristic is temperature dependent and has per device variation. Hence LED drivers are usually constant-current sources, ie they measure and attempt to regulate the current.
>One awful thing cheap LED lights do is blink slowly to control their voltage
I assume you're talking about PWM. That's not just to be cheap. It's the only real way to control brightness.