A novel approach to multi-hop routing for cognitive random access is developed under channel gain uncertainty constraints. Motivated by the inherent randomness of the propagation medium, the novel routing strategy leverages pairwise decoding probabilities to randomly route packets to neighboring nodes. The resultant cross-layer optimization framework not only provides optimal routes in a well-defined sense, but also yields transmission probabilities and transmit-powers, thus enabling cognizant adaptation of networking, medium access, and physical layer parameters to the operational environment. The relevant optimization problem is non-convex and hence hard to solve in general. Nevertheless, a successive convex approximation approach is employed to efficiently find a Karush-Kuhn-Tucker solution. Enticingly, the fresh look advocated here permeates benefits also to conventional multi-hop random access networks in the presence of channel uncertainty.