How strong of a power supply is needed?
That depends on the age of the machine (a pentium 4 is also very demanding) but for a single 58xx card usually a 400-500 watt psu has a sufficently sized 12v rail, one like this is on the lower end of the spectrum it would handle a single 58xx or a pair of 57xx without too much trouble
http://www.newegg.com/Product/Product.aspx?Item=N82E16817182202Be careful with PSU: I've recently bought a 650W one for one 5850 and it gave most of the power to the 5V, 3.3V lines and only a small fraction to 12V. So it was useless for my mining purposes.