We address the statistical mechanics of randomly and permanently crosslinked networks. We develop a theoretical framework (vulcanization theory) which can be used to systematically analyze the correlation between the statistical properties of random networks and their histories of formation. Generalizing the original idea of Deam and Edwards, we consider an instantaneous crosslinking process, where all crosslinkers (modeled as Gaussian springs) are introduced randomly at once in an equilibrium liquid state, referred to as the preparation state. The probability that two functional sites are crosslinked by a spring exponentially decreases with their distance squared. After formally averaging over network connectivity, we obtained an effective theory with all degrees of freedom replicated 1 + n times. Two thermodynamic ensembles, the preparation ensemble and the measurement ensemble, naturally appear in this theory. The former describes the thermodynamic fluctuations in the state of preparation, while the latter describes the thermodynamic fluctuations in the state of measurement. We classify various correlation functions and discuss their physical significances. In particular, the memory correlation functions characterize how the properties of networks depend on their history of formation, and are the hallmark properties of all randomly crosslinked materials. We clarify the essential difference between our approach and that of Deam-Edwards, discuss the saddle-point order parameters and its physical significance. Finally we also discuss the connection between saddle-point approximation of vulcanization theory, and the classical theory of rubber elasticity as well as the neo-classical theory of nematic elastomers.