I immersed 2 nails in salt water and hooked them up to my DC power supply. I got some serious rust in about an hour. The more salt you add (up to the point where no more will dissolve), the more current will flow, and the faster the rust will form. Just keep in mind that, with a battery, it will discharge rapidly if you use a lot of salt and leave it connected for a long time.
Make sure you don't let the nails touch each other, especially if you are using a supply with no current limiting, like a battery. It might be prudent to put a 100 ohm resistor, capable of dissipating 2 watts, in series with one of the nails unless you can be certain that the nails won't touch.