In this paper, we derive fundamental performance limits of underwater (UW) networks via an analysis of the average behavior of random deployments. In particular, we consider an UW network that consists of a Poisson point process of transmitters, each with a receiver at a given distance. The link channel model accounts for path-loss, frequency-dependent absorption, and Rayleigh fading. We evaluate the probability of a successful transmission, defined as the probability that the signal-to-interference-and-noise ratio at the typical receiver is greater than a predetermined threshold, over different network and channel realizations. We then determine the network throughput density and the transmission capacity, defined as the maximum throughput density such that a constraint on the success probability is satisfied. The dependence of these metrics on the operating frequency and other system parameters is quantified through the proposed framework.