We performed an unbiased structure search for low-lying energetic minima of neutral and charged palladium Pdn(Q) (n = 2-20, Q = 0, + 1 and -1) clusters using CALYPSO method in combination with density functional theory (DFT) calculations. The main candidates for the lowest energy neutral, cationic and anionic clusters are identified, and several new candidate structures for the cationic and anionic ground states are obtained. It is found that the ground state structures of small palladium clusters are more sensitive to the charge states. For the medium size Pdn(0/+/-) (n = 16-20) clusters, a fcc-like growth behavior is found. The structural transition from bilayer-like structures to cage-like structures is likely to occur at n = 14 for the neutral and cationic clusters. In contrast, for the anionic counterparts, the structural transition occurs at Pd13(-). The photoelectron spectra (PES) of palladium clusters are simulated based on the time-dependent density functional theory (TD-DFT) method and compared with the experimental data. The good agreement between the experimental PES and simulated spectra provides us unequivocal structural information to fully solve the global minimum structures, allowing for new molecular insights into the chemical interactions in the Pd cages.