Millimeter-wave (mmWave) cellular systems are power-limited and susceptible to blockages. As a result, mmWave connectivity will be likely to be intermittent. One promising approach to increasing mmWave connectivity and range is to use relays. Device-to-device (D2D) communications open the door to the vast opportunities of D2D and device-to-network relaying for mmWave cellular systems. In this correspondence, we study how to select a good relay for a given source-destination pair in a two-hop mmWave cellular system, where the mmWave links are subject to random Bernoulli blockages. In such a system, probing more relays could potentially lead to the discovery of a better relay but at the cost of more overhead. We find that the throughput-optimal relay probing strategy is a pure threshold policy: the system can stop relay probing once the achievable spectral efficiency of the currently probed two-hop link exceeds some threshold. In general, the spectral efficiency threshold can be obtained by solving a fixed point equation. For the special case with on/off mmWave links, we derive a closed-form solution for the threshold. Numerical results demonstrate that the threshold-based relay probing strategy can yield remarkable throughput gains.