If you are shooting from scratch, choose the highest one. That way you can enlarge if necessary. Having said that, my old 1.3 megapixel (1280x960) gave consistantly good resolution for 4x6 output.
I did find that higher resolution helped with low exposure noise in poorly lit environments. You have a new Nikon coolpix, no?