In this paper, we provide a complete study on the training based channel estimation issues for relay networks that employ the amplify-and-forward (AF) transmission scheme. We first point out that separately estimating the channel from source to relay and relay to destination suffers from many drawbacks. Then we provide a new estimation scheme that directly estimates the overall channels from the source to the destination. The proposed channel estimation well serves the AF based space time coding (STC) that was recently developed. There exists many differences between the proposed channel estimation and that in the traditional single input single out (SISO) and multiple input single output (MISO) systems. For example, a relay must linearly precode its received training sequence by a sophisticatedly designed matrix in order to minimize the channel estimation error. Besides, each relay node is individually constrained by a different power requirement because of the non-cooperation among all relay nodes. We study both the linear least-square (LS) estimator and the minimum mean-square-error (MMSE) estimator. The corresponding optimal training sequences, as well as the optimal preceding matrices are derived from an efficient convex optimization process.