|MadSci Network: Astronomy|
The simple answer to your question is that it depends on how hard you look! The record for seeing the new Moon is only about 12 hours after it was new (that is, completely dark). However, it only becomes obvious after a day or two, when the cresent becomes bright enough to easily be seen by the naked eye. The trouble is that at or near new Moon, the Moon is very close to the Sun in the sky. So to spot it you need to wait until after sunset, and then look very close to the horizon; normally things like trees and houses will get in the way, so to see the earliest Moon possible get high up, or better still somewhere with an ocean view.
Try the links in the MadSci Library for more information on Astronomy.