Gain is absolutely the ONLY important part of PSRR. Essentially what you are saying is how much can an op-amp when feeding back a signal cancel out any ripples introduced from the power supply, not from the input of the circuit..
Lets take a simple example: an ideal (infinite open loop gain) voltage follower (output tied directly to the inverting input, fed from the non inverting input). The circuit has a closed loop gain of 1, but the feedback (since the overall gain is SOOO high) will mean that any power supply ripple will be canceled due to the feedback forcing the non inverting and inverting inputs to be in perfect lockstep..
But take the SAME example, but make the OPEN loop gain of the opamp 1, still with closed loop gain of 1, then suddenly the op amp can't keep up with the changes between the non-inverting input and the output-inverting input. And hence all ripple from the power supply would be visible on the output (essentially the op-amp would turn into a noise source with the noise being the coupled power supply ripple)
I understand HOW stevenvh could say that the gain is not meaningful, because he meant CLOSED loop gain... But the gain of question is OPEN loop gain, and YES, that is EVERYTHING in PSRR.
EDIT: And to answer your question, just to follow up slightly here, the PSRR is related to open loop gain, but the more closed loop gain you introduce, the more power supply ripple you will get on the output (hence the 60dB you reference above)
Here is why: Same example I give above, except this time you have a REAL op amp, (finite open loop gain), and resistors in your feedback path, meaning you have a closed loop gain of some value, say 6dB. Since the resistors behave as a voltage divider, the op-amp has to OVERCOMPENSATE for the power supply ripple being fed back to the non-inverting input. If it can only compensate for 100dB of power supply ripple, you will only get 94dB of rejection. The more closed loop gain you introduce, the less of the power supply ripple you are able to reject.
The whole conversation stems from the separate meanings of open loop and closed loop gain.
2nd EDIT: And the way that you get 60dB, or I get my 94dB is that you have to realize you have to convert dB BACK so for example you need to use
$$
20 \log10\left(\frac{10^\frac{100}{20}}{10^\frac{6}{20}}\right) = 94 \mathrm{dB}
$$
$$
20 \log10\left(\frac{10^\frac{100}{20}}{10^\frac{40}{20}}\right) = 60 \mathrm{dB}.
$$
And YES the other guy who said it should be 1mV not 1µV on Wikipedia is correct.
You have the right idea for a basic unregulated supply. A transformer, four diodes, and as large a cap as you can manage will serve well enough for a lot of purposes, but isn't appropriate for all.
There are two main problems with such a unregulated supply. First, the voltage is not known well. Even with ideal components, so that the AC coming out of the transformer is a fixed fraction of the AC going in, you still have variations in that AC input. Wall power can vary by around 10%, and that's without considering unusual situations like brownouts. Then you have the impedance of the transformer. As you draw current, the output voltage of the transformer will drop.
Second, there will be ripple, possibly quite significant ripple. That cap is charged twice per line cycle, or every 8.3 ms. In between the line peaks, the cap is supplying the output current. This decreases the voltage on the cap. The only way to decrease this ripple in this type of design is to use a bigger cap or draw less current.
And don't even think about power factor. The power factor a full wave bridge presents to the AC line is "not nice". The transformer will smooth that out a little, but you will still have a crappy power factor regardless of what the load does. Fortunately, power factor is of little concern for something like a bench supply. Your refrigerator probably treats the power line worse than your bench supply ever will. Don't worry about it.
Some things you can't do with this supply is run a anything that has a tight voltage tolerance. For example, many digital devices will want 5.0 V or 3.3 V ± 10%. You're supply won't be able to do that. What you should probably do is aim for 7.5 V lowest possible output under load, with the lowest valid line voltage in, and at the bottom of the ripples. If you can guarantee that, you can use a 7805 regulator to make a nice and clean 5 V suitable for digital circuits.
Note that after you account for all the reasons the supply voltage might drop, that the nominal output voltage may well be several volts higher. If so, keep the dissipation of the regulator in mind. For example, if the nominal supply output is 9 V, then the regulator will drop 4 V. That 4 V times the current is the power that will heat the regulator. For example, if this is powering a digital circuit that draws 200 mA, then the dissipation in the regulator will be 4V x 200mA = 800mW. That's will get a 7805 in free air quite hot, but it will probably still be OK. Fortunately, 7805 regulators contain a thermal shutdown circuit, so they will just shut off the output for a while instead of allowing themselves to get cooked.
Best Answer
The reason why PSR is important even in battery supplied devices is that one can (and usually) have several different kinds of circuits supplied from the same battery in the same device. Due to internal resistance of the battery, changes in the current consumption of the one part of the device will be seen as voltage variation for all the circuitry supplied by thereof.
One dramatic example is GSM phone, where power amplifier for transmitter will consume significant amount of current (amps range) every time the frame is transmitted with almost no current consumption in between frames. Assuming* 0.5 Ohm internal resistance and 1A consumption that means 500mV voltage variation repeating several hundreds times a second.
*) those are example numbers, too lazy to check actual GSM numbers