In this paper, we consider the multichannel rendezvous problem in cognitive radio networks (CRNs) where the probability that two users hopping on the same channel have a successful rendezvous is a function of channel states. The channel states are modeled by stochastic processes with joint distributions known to users. However, the exact state of a channel at any time is not observable. We first consider two channel models: (i) the fast time-varying channel model (where the channel states are assumed to be independent and identically distributed in each time slot), and (ii) the slow time-varying channel model (where the channel states remain unchanged over time). Among the classes of the blind rendezvous policies that randomly hop on channels according to certain channel selection probabilities, we show the optimal channel selection policy that minimizes the expected time-to-rendezvous (ETTR) is the single selection policy that hops on the ``best'' channel all the time in the fast time-varying channel model. However, for the slow time-varying channel model, it is much more difficult to find the optimal channel selection policy. By using the majorization ordering, we derive a lower bound and an upper bound for the ETTR under the assumption that the channel states are exchangeable random variables. Bases on these bounds, we then prove various approximation solutions. We then extend our results to general channel models where the joint distribution of the channel states is only assumed to be stationary in time.