This paper exploits the inherent cyclostationarity of linearly modulated signals, transmitted through fading channels, to design robust blind and data-aided mobile speed estimators. Two categories of cyclic-correlation- and cyclic-spectrum-based methods are developed. Extension to space-time speed estimation at the base station in macrocells is also provided. In comparison with the existing methods, the new estimators can be used without any need for pilot tones, and are robust to additive stationary noise or interference of any color or distribution. The performance of the proposed estimators are illustrated via extensive Monte Carlo simulations.