This paper studies coverage maximization for cellular networks in which base station (BS) locations are modeled using a homogenous spatial Poisson point process, and user locations are arbitrary. A user is covered for communication if its received signal-to-interference-plus-noise-ratio (SINR) is above a given threshold value. Two coverage models are considered. In the first model, the coverage of a user is determined based on the received SINR only from the nearest BS. The nearest BS happens to be the BS maximizing the received SINR without fading. In the second model, on the other hand, the coverage of a user is determined based on the maximum SINR from all BSs in the network. The objective is to maximize the coverage probability under the constraints on transmit power density (per unit area). Using stochastic geometry, coverage probability expressions for both coverage models are obtained. Using these expressions, bounds on the coverage maximizing power per BS and BS density are obtained. These bounds truncate the search space of the optimization problem, and thereby simplify the numerical evaluation of optimum BS power and density values considerably. All results are derived for general bounded path loss models satisfying some mild conditions. Specific applications are also illustrated to provide further insights into the optimization problem of interest.