We study the problem of detecting a structured, low-rank signal matrix corrupted with additive Gaussian noise. This includes clustering in a Gaussian mixture model, sparse PCA, and submatrix localization. Each of these problems is conjectured to exhibit a sharp information-theoretic threshold, below which the signal is too weak for any algorithm to detect. We derive upper and lower bounds on the threshold by applying the first and second moment methods. Our bounds differ by at most a factor of root two when the rank is high or the signal matrix is very sparse. Moreover, our upper bounds show that there is a significant regime where reliable detection is information-theoretically possible but where known algorithms such as PCA fail completely, since the spectrum of the observed matrix is uninformative. Next, in a toy sparse PCA model, using an interpolation method proposed by Guerra, we prove the Bethe mutual information (related to Bethe free energy) yields an upper bound to the exact mutual information, making a step forward in precisely locating the phase transition threshold. This work is at the intersection of information theory, statistics, and statistical physics. Based on joint work, available at arXiv:1607.05222 and arXiv:1603.08447, with Jess Banks, Florent Krzakala, Cristopher Moore, Roman Vershynin, and Lenka Zdeborova.