The design of medium access control protocols for a cognitive user wishing to opportunistically exploit frequency bands within parts of the radio spectrum having multiple bands is considered. In the scenario under consideration, the availability probability of each channel is unknown a priori to the cognitive user. Hence efficient medium access strategies must strike a balance between exploring the availability of channels and exploiting the opportunities identified thus far. Using a sequential design approach, an optimal medium access strategy is derived. To avoid the prohibitive computational complexity of this optimal strategy, a low complexity asymptotically optimal strategy is also developed. The proposed strategy does not require any prior statistical knowledge about the traffic pattern on the different channels.