Methods, apparatus and systems for implementing link training for next-generation high-speed Ethernet links including a 100 Gbps Ethernet link. Training frames are transmitted from a transmit port to be received at a receive port, with each training frame comprising a frame marker portion, a control channel portion, and a training pattern portion. Four-level signaling including a low level signal, first and second intermediate level signals, and a high level signal is implemented for the training pattern portion of the training frame using a pseudo-random bit pattern, while only the low and high level signals are employed for the frame marker and control channel portions of the training frame. The four-level signaling may employ PAM4 encoding. Examples of apparatus and systems in which the link training techniques may be implemented include blade servers and network routers and switches.