This paper investigates the problem of maximally utilizing the spectrum opportunities in cognitive radio networks with multiple potential channels. In particular, the optimal sensing order problem in multi-channel cognitive medium access control with opportunistic transmissions is studied. It is first shown that, when the potential channels are identical (except for the availability probabilities) and independent, the intuitive sensing order (i.e., descending order of the channel availability probabilities) does not lead to optimality in general. A dynamic programming approach for the search of optimal sensing order is then presented. Finally, for some special cases, it is proved that a simple optimal sensing order does exist.