How to improve load transient response of an LM317 voltage-regulator powering an audio amplifier?
Is it correct to assume that an ideal (theoretical) PSU for audio applications should produce a constant voltage regardless of load variations (i.e. it is a voltage source)?


Yes. An ideal power supply for any application should be an ideal voltage source, which has a constant voltage.


  In practice, what are acceptable levels of supply voltage variation due to transients in an audio application (in percentage of Vs or mV)?


This is dependent on your application. You have to evaluate your desired noise/distortion, the power supply rejection of the audio components you are using, and the way the circuit is constructed. 0.1% power supply variation translates to a -60dB noise floor, which might be sufficient.


  What is the correct approach to reduce these V swings? Should I place a capacitor on the INPUT or OUTPUT of the regulator? Is there a rule of thumb/calculation for the required capacitance? Are electrolytic capacitors OK, or should I use polyester or tantalum caps (i.e. something with a lower ESR)?


Probably both. You should have both bulk capacitance on the output and low-ESR decoupling caps in close proximity to all active chips (op-amps, ADCs, DACs, etc). And some more capacitance on the input certainly wouldn't hurt.

Typically, you might use large electrolytics for bulk capacitance, and low-ESR ceramics for faster decoupling. Again, how much you need depends on the magnitude and characteristics of the wiggles on the supply rail. Also, carefully read the datasheet of the regulator and make sure you are within its comfortable operating region: the regulator has a response speed and current limits, as well as input ripple rejection specs.