We study learning-based energy-efficient multi- user scheduling of delay-sensitive data over fading channels. To tradeoff energy and delay, we combine adaptive rate transmission at the physical layer with a rate-adaptive medium access control (MAC) protocol based on carrier sense multiple access with collision avoidance (CSMA/CA). We formulate the multi-user scheduling problem as a constrained Markov decision process (CMDP). We show that the multi-user problem is intractable and propose to decompose it into multiple (coupled) single-user problems. We design a reinforcement learning algorithm to solve the single-user problems online so that users can achieve energy-efficient operation while meeting their delay constraints, even though the channel, traffic, and multi-user dynamics are unknown a priori. Our proposed MAC protocol enables users to meet significantly tighter delay constraints while also consuming less energy than under the 802.11 Distributed Coordination Function (DCF). Moreover, the proposed learning algorithm converges significantly faster than a state-of-the-art solution.