Metal patinas are a whole art unto themselves. I have used ammonia for brass, made stains with vinegar and so on. Sculptors spend a lot of time on this topic.
Assuming your nails contain iron, then you are trying to form ferrous oxide, the black 'rust' (as opposed to the orange rust, ferric oxide). Almost any acid will do the trick. Acetic acid (vinegar) and bleach is very effective - mind the fumes; they are dangerous.
You can also buy a premixed pickle. There are many, I would recommend http://www.jaxchemicals.com/ if you wish to go that way. They sell a Iron, Steel, and Nickel Blackener in a pint size (among others).
Also keep in mind that heating the nails via a torch or similar flame will also change the color, which is a quick and cheap path.
If you have a grinder, grinding the nail head can overheat the metal and discolor it. Obviously, this leaves marks. You can use a hammer (a chasing hammer if you are feeling fancy) to change the texture of the nail without loosing the patina. Buy this method, you can create nails that look like they were hand wrought very quickly.