The cooling and heating of palladium clusters Pd-13 and Pd-55 by binary collisions with atoms of a surrounding helium gas are studied by means of molecular dynamics simulation. The efficiency of the collisional energy transfer is determined as a function of cluster and gas temperature and of cluster phase, the cluster being in either a solid or a liquid phase. A simple statistical analysis is presented for the energy transfer between a cluster and a rare gas atom. The analysis is based on an ergodic collision assumption of microcanonical relaxation in each collision. The deviation from this limiting law is collected in a collision efficiency factor which reflects incomplete energy redistribution during the lifetime of the collision complex. The thermal energy and change in heat capacity observed for the clusters at the freezing (melting) transition is accounted for by a parametrized density of states reflecting separate contributions from a solid and a molten structure. The same density of states Is then used in the ergodic collision theory for the analysis of energy transfer.