In a cooperative wireless network with multiple relay nodes, opportunistic relay selection (ORS) protocols exploit the distributed spatial diversity while maintaining a constant multiplexing loss. However, the ORS protocols require the knowledge of network channel state information (CSI) at the destination and feedback of best relay node index. The overhead incurred in estimation and feedback of CSI increases linearly with the number of relays. Assuming a block fading model in which the fading remains constant over a given number of channel uses, in this work we investigate the amount of training needed to minimize the outage probability of mutual information (MI) with both amplify-and-forward (fixed and variable gain) as well as decode-and-forward relay signal processing. Since exact expressions for the MI outage probability are difficult to obtain, we derive upper bounds on MI outage probability using a well-known “worst-case noise distribution” argument. We also determine optimum power split between training and data phases at each transmitter, and present some numerical results showing the impact of practical channel estimation on the outage probability of ORS protocols.