We discuss the various ways in which primordial black holes may have formed in the early Universe and how the effects of such black holes can be used to place constraints on cosmological models. We show that such constraints may be severely modified if the value of the gravitational "constant" G varies with cosmological epoch, a possibility which arises in many scenarios for the early Universe. The nature of the modification depends upon whether the value of G near a black hole maintains the value it had at its formation epoch (corresponding to gravitational memory) or whether it tracks the background cosmological value. This is still uncertain but we discuss various approaches which might help to resolve the issue.

17 pages, 4 figures available from author, to appear in Proceedings of "Black Holes and Gravitational Waves" (Kyoto 1999)