Molecular dynamics simulations were performed on series of gold nanoclusters comprised of 459, 1157, and 3943 atoms, to study their structures and properties during heating and cooling. The increased depression of melting point as particle size decreases has been interpreted in terms of Pawlow's triple point theory, the liquid shell model, and extensions of the two. The solid-liquid interfacial free energy sigma (sl) of similar to0.15 J/m(2) inferred from the liquid shell model was close to the values predicted by several empirical relations. When molten particles in a given series were frozen, several different final structures were obtained even though conditions had been identical. Most of the frozen clusters attained an icosahedral structure, a structure found to be stable to mild annealing. Other structures observed were imperfect truncated decahedra, twinned truncated octahedra, and hexagonal close packed structures. The rate of crystal nucleation in liquid clusters was analyzed in terms of classical nucleation theory and the diffuse interface theory. The interfacial free energy of 0.084 J/m(2) inferred from the kinetics of freezing was appreciably lower than that inferred from the melting points. Since existing theories of the melting of small particles and the nucleation of crystals in them are far from rigorous, a close agreement between the quasi-thermodynamic and kinetically based free energies cannot be taken for granted. Sources of error in the models of melting are discussed.