Any hint of non-Gaussianity in the cosmological initial conditions will provide us with a unique window into the physics of the early Universe. We show that the impact of a small local primordial non-Gaussianity (generated on superhorizon scales) on the statistics of collapsed objects (such as galaxies or clusters) can be approximated by using slightly modified, but Gaussian, initial conditions, which we describe through simple analytic expressions. Given that numerical simulations with Gaussian initial conditions are relatively well studied, this equivalence provides us with a simple tool to predict signatures of primordial non-Gaussianity in the statistics of collapsed objects. In particular, we describe the predictions for non-Gaussian mass function, and also confirm the recent discovery of a nonlocal bias on large scales [N. Dalal, O. Dore, D. Huterer, and A. Shirokov, Phys. Rev. D 77, 123514 (2008).][S. Matarrese and L. Verde, Astrophys. J. 677, L77 (2008).], as a signature of primordial non-Gaussianity. We then study the potential of galaxy surveys to constrain non-Gaussianity using their autocorrelation and cross correlation with the cosmic microwave background (CMB) (due to the integrated Sachs-Wolfe effect), as a function of survey characteristics, and predict that they will eventually yield an accuracy of ΔfNL∼0.1 and 3, respectively, which will be better than or competitive with (but independent of) the best predicted constraints from the CMB. Interestingly, the cross correlation of the CMB and the NRAO VLA Sky Survey galaxy survey already shows a hint of a large local primordial non-Gaussianity: fNL=236±127.