The interaction of PdN clusters (N = 2, 3, 4, 7, and 13) with multiple H2 adsorbate molecules is investigated using density functional theory with the hybrid PBE0 functional. The optimal structure for each PdNH2(L) complex is determined systematically via a sequential addition of H2 units. The adsorption energy for each successive H2 addition is computed to determine the maximum number of molecules that can be stably added to a PdN at T = 0 K. The Gibbs free energy is then used to determine the saturation coverage at finite temperature. For N = 2, 3, and 4, a single H2 is found to dissociate, and up to two additional molecular H2 units per Pd atom can bind stably to the clusters at 0 K. At 300 K, one H2 unit dissociates, and only one additional H2 molecular unit per Pd atom is stably bound. For N = 7 and T = 0 K, two H2 units dissociate, and 11 additional H2 units bind molecularly. At 300 K, two units dissociate, and eight are bound molecularly. For N = 3, 4, and 7, we find that an additional H2 unit may dissociate if the underlying cluster structure rearranges. Eight H2 units dissociate on Pd13 at 0 K. At least one additional H2 binds molecularly at 0 K, but none bind at 300 K. This suggests that only dissociated H2 units will stably bind to larger Pd particles at room temperature. The influence of molecularly adsorbed H2 units on the migration of dissociated H atoms is investigated in a preliminary way. Both barrier heights and the relative stability of local minima of Pd4H2(L) are found to be affected by the degree of molecular H2 coverage.