Photoelectron spectroscopy is used to investigate aluminum dideuteride cluster anions, AlnD2- (n=3,6-15), produced by laser vaporization of a pure Al target with a D2-seeded helium carrier gas. Comparison between the well-resolved photoelectron spectra of AlnD2- and Aln- reveals the nature of interactions between D2 and Aln-. Depending on the size of the Aln- clusters and their electronic structure, three types of AlnD2- species are observed, dideuteride (dissociative chemisorption), molecular chemisorption, and physisorption. Striking spectral similarities are observed between photoelectron spectra of AlnD2- and Aln- for n=9, 11, 13, and 15, suggesting that D2 is physisorbed on these closed-shell Aln- clusters. For AlnD2- with n=3, 6, 7, and 10, completely different spectra are observed in comparison with the corresponding Aln- clusters, suggesting that the AlnD2- species may be characterized as dideuterides. For AlnD2- with n=8, 12, and 14, in which the Aln- clusters are open shell, the D2 is characterized as chemisorption on the basis of spectral shifts and similarities relative to those of the corresponding Aln- clusters.