This chapter examines the public legitimacy of artificial intelligence governance (AIG) by synthesising the existing comparative, survey-based literature. We conceptualise legitimacy sociologically, encompassing the input, throughput, and output dimensions of AI-affected democratic decision-making. Reviewing evidence across countries and use cases, we show that legitimacy perceptions hinge on perceived transparency, fairness, accountability, performance, and distributive outcomes, yet vary by culture, knowledge, values, and trust in institutions and AI. Publics remain ambivalent. Awareness is uneven, politicisation is nascent, and experts and affected groups often diverge from the general public. Communication environments and participation formats shape attitudes, but superficial public involvement risks backlash. We map four research frontiers: addressing Euro-Atlantic bias by integrating Global South perspectives; decomposing layered trust across governments, companies, scientific bodies, and AI; tracing salience and politicisation and their shifts from output to input legitimacy criteria; and examining agentic systems and synthetic relationships that may reconfigure accountability, responsibility, and oversight.