Rechargeable aluminum batteries are an emerging energy storage technology with great potential due to the high capacity, global abundance, low cost, and inherent safety of aluminum metal. However, few cathode materials have been demonstrated that exhibit high energy density and cycle life, in part due to the challenges associated with the high charge density of trivalent aluminum cations and the highly reactive nature of the chloroaluminate-containing ionic liquids commonly used as electrolytes. Here, investigations of selected intercalation and conversion cathodes for rechargeable aluminum metal batteries will be presented, including crystalline transition metal compounds, graphite, and sulfur-containing materials. Molecular-scale understanding of their charge storage mechanisms will be discussed, revealed by a combination of electrochemical methods, solid-state magic-angle-spinning (MAS) NMR spectroscopy, in situ diffraction methods, and electron microscopy. Intrinsic challenges—and opportunities—associated with intercalation and conversion cathode materials will be discussed. Overall, the results yield insights into possible rational design strategies for developing next-generation cathode materials for rechargeable aluminum metal batteries with improved energy densities, rate capabilities, and cycle lifetimes.