This paper considers distributed opportunistic scheduling (DOS) with cooperative relaying in wireless ad hoc networks, with a focus on characterizing the desired tradeoff between the probing cost for establishing cooperative relaying and the higher throughput via opportunistic cooperative networking. Specifically, distributed scheduling and probing for cooperative relaying is treated as an optimal stopping problem with two levels of incomplete information. Cases with or without dedicated relays are considered, and the existence of the optimal strategies for both cases are established. Then, it is shown that for the case with dedicated relays, the optimal strategy exhibits a threshold structure, in which it is optimal to probe the dedicated relay when the signal-to-noise ratio (SNR) of the source-relay link exceeds some threshold. For the case without dedicated relays, under more restrictive conditions, the optimal strategy is also threshold-based, in the sense that it is optimal to probe potential relays when the SNR of the source-destination link lies between two thresholds. Furthermore, these strategies can be implemented in a distributed manner.