Wireless sensor networks(WSNs) have a diverse set of applications such as military surveillance, health and environmental monitoring, and home automation. Sensor nodes are equipped with pre-charged batteries, which drain out when the nodes sense, process, and communicate data. Eventually, the nodes of the WSN die and the network dies. Energy harvesting(EH) is a green alternative to solve the limited lifetime problem in WSNs. EH nodes recharge their batteries by harvesting ambient energy such as solar, wind, and radio energy. However, due to the randomness in the EH process and the limited amounts of energy that can be harvested, the EH nodes are often intermittently available. Therefore, even though EH nodes live perpetually, they do not cater to the network continuously. We focus on the energy-efficient design of WSNs that incorporate EH, and investigate the new design trade-offs that arise in exploiting the potentially scarce and random energy arrivals and channel fading encountered by the network. To this end, firstly, we compare the performance of conventional, all-EH, and hybrid WSNs, which consist of both conventional and EH nodes. We then study max function computation, which aims at energy-efficient data aggregation, in EH WSNs. We first argue that the conventional performance criteria used for evaluating WSNs, which are motivated by lifetime, and for evaluating EH networks are at odds with each other and are unsuitable for evaluating hybrid WSNs. We propose two new and insightful performance criteria called the k-outage and n-transmission durations to evaluate and compare different WSNs. These criteria capture the effect of the battery energies of the nodes and the channel fading conditions on the network operations. We prove two computationally-efficient bounds for evaluating these criteria, and show their use in a cost-constrained deployment of a WSN involving EH nodes. Next, we study the estimation of maximum of sensor readings in an all-EH WSN. We analyze the mean absolute error(MAE) in estimating the maximum reading when a random subset of the EH nodes periodically transmit their readings to the fusion node. We determine the optimal transmit power and the number of scheduled nodes that minimize the MAE. We weigh the benefits of the availability of channel information at the nodes against the cost of acquiring it. The results are first developed assuming that the readings are transmitted with infinite resolution. The new trade-offs that arise when quantized readings are instead transmitted are then characterized.Our results hold for any distribution of sensor readings, and for any stationary and ergodic EH process.