Capacitors probably make the most difference to the sound by being used in ways they should not be (e.g. undersized coupling capacitors, large AC voltage falling on polarized electrolytic capacitors with not enough DC offset on them to prevent "wrong" polarity, very non-linear capacitors used in places where they have a significant effect on the sound (e.g. passive crossovers, equalizers, tone controls), etc.). That is, a good design tries to minimize the effect capacitors can have in the first place, and where they are really needed, it uses ones of the right type and capacitance. Very expensive "audiophile" capacitors are probably mostly snake oil.
Other than obviously the frequency response, electrolytic coupling capacitors mostly affect the bass distortion (basically, the larger the AC voltage swing on the capacitor is, the more it distorts, and it has higher impedance at lower frequencies, so the voltage will be higher there when connected serially with a load), however, it is likely that bass roll-off becomes audible sooner than the distortion. There are claims regarding the effect of capacitors on sound stage, dynamics, and other (often vaguely defined) parameters of the sound, but I have not seen these proven or convincingly explained.
As a random example, here is the THD vs. frequency and 60+7000 Hz 4:1 intermodulation distortion of a cheap sound card that uses "no name" surface mount 220 uF electrolytic capacitors on its line output. Both were tested at full scale (slightly less than 2 Vrms), and the red trace is the most difficult case, with a total load impedance of only 122 Ω), while the yellow is an easier high impedance line input. I doubt anyone would be able to hear this, and at 20 Hz, where the THD is -84 dB (= 0.0063%), there is already 0.5 dB roll-off; with smaller capacitors and/or lower impedance load, there would be higher distortion, but also more roll-off. At higher frequencies, much of the increased distortion comes from the op-amp buffer driving the line output.
Of course, an important parameter of electrolytic capacitors in particular is how long they last. Maybe the cheaper ones can have a real disadvantage here.
It would be interesting to do more measurements (especially ones, where, unlike above, the performance of the capacitor is more clearly isolated from the rest of the system), and loopback based ABX tests with various capacitors in different test configurations. However, I think audible differences would only occur with really poor or faulty ones, in "difficult" applications, badly designed circuits, or with a wrong choice of capacitor for the application.
