In cognitive radio (CR) networks, medium access control (MAC) protocols play an important role to exploit the spectrum opportunities, manage the interference to primary users (PUs), and coordinate the spectrum access amongst secondary users (SUs). In this paper, we first introduce the challenges in the design and implementation of CR MAC protocols. Then, we make a comprehensive survey of the state-of-the-art CR MAC protocols and categorize them on the basis of spectrum sharing modes, i.e., overlay and underlay modes. We also introduce some other classification metrics such as architecture (centralized or distributed), sharing behaviors (cooperative or non-cooperative), and access modes (contention based or contention free). Through the study, we find out that most CR MAC protocols are designed for the overlay mode. The CR MAC protocols in underlay mode could yield higher spectrum utilization efficiency with the cost of more complicated power and admission control schemes. The centralized CR MAC protocols are more suitable to do spectrum sensing using quiet period of whole network, while the distributed CR MAC protocols are more flexible to deploy. We identify several future directions, such as more practical CR MAC protocols for underlay mode, MAC protocols considering security, MAC protocols considering heterogeneous coexistence, etc.