An energy harvesting (EH) transmitter communicating over a time-correlated wireless channel is considered. The transmitter is capable of sensing the current channel state, albeit at the cost of both energy and transmission time. The EH transmitter aims to maximize its long-term throughput by choosing one of the following actions: 1) defer its transmission to save energy for future use; 2) transmit reliably at a low rate; 3) transmit at a high rate; and 4) sense the channel to reveal the channel state at a cost of energy and transmission time, and then decide to defer or to transmit. The problem is formulated as a partially observable Markov decision process with a belief on the channel state. The optimal policy is shown to exhibit a threshold behavior on the belief state, with battery-dependent threshold values. The optimal threshold values and performance are characterized numerically via the value iteration algorithm as well as a policy search algorithm that exploits the threshold structure of the optimal policy. Our results demonstrate that, despite the associated time and energy cost, sensing the channel intelligently to track the channel state improves the achievable long-term throughput significantly as compared to the performance of those protocols lacking this ability as well as the one that always senses the channel.