This paper considers the design of medium access control protocols for cognitive radio networks in a highly dynamic environment. In the scenario under consideration, multiple cognitive users seek to opportunistically exploit the availability of empty frequency bands within parts of the radio spectrum having multiple bands. The availability of each channel is modelled as a Markov chain. The scenario in which the parameters of the Markov chain of each channel is known is first considered. An optimal symmetric strategy that maximizes the total throughput of the cognitive users is developed. Next, the situation in which the parameters of each channel are unknown a priori is considered. This problem is modelled as a competitive multiuser bandit problem, a non-trivial extension of the classical bandit problem. Low complexity medium access protocols, which strike an optimal balance between exploration and exploitation in such competitive environments, are developed. The operating points of these low complexity protocols are shown to converge to those of the scenario in which the parameters are known.