This paper addresses the recovery of multilevel signals in the presence of frequency nonselective fading and additive white Gaussian noise. We first propose a novel detector which performs approximate noncoherent maximum likelihood estimation for slowly fading channels, where the channel gain and phase remain constant over several symbol durations. This maximum likelihood detector for signals with unknown amplitude and phase (ML-UAP) is then modified and implemented recursively using the Viterbi algorithm (VA) to obtain a lower complexity suboptimal noncoherent VA for multilevel signals (SNVA-M). Next, a forgetting-factor is introduced to deal with variations in gain and phase due to fast fading. The resulting forgetting-factor-based SNVA-M (FSNVA-M) does not require explicit carrier recovery or automatic gain control (AGC) procedures. The SNVA-M and the FSNVA-M detectors perform as well as a coherent detector for AWGN channels and for fast Rician fading channels, but are not suitable for fast Rayleigh fading channels. For fast fading Rayleigh channels, we propose three schemes based on the detection of differentially encoded circular 8-QAM. Although these schemes are suboptimal when compared to various other optimal receivers proposed for flat fading Rayleigh channels, they do not require the knowledge of the fade statistics and are computationally more efficient. We refer to these techniques as the symbol-by-symbol differential detector for multilevel signals (SSDD-M), multiple symbol differential detector using VA for multilevel signals (MSDDVA-M) and the quotient space VA (QSVA) approach. The simulated error-rate performance of these three approaches for differentially encoded 8-QAM are found to perform better than the conventional detector for differentially encoded 8-PSK in fast fading Rayleigh channels. Moreover, the proposed detectors are highly suited for DSP-based receiver implementations.