This is the first paper in a series of four dealing with the adsorption site, electronic structure, and chemistry of small Au clusters, Au(n) (n=1-7), supported on stoichiometric, partially reduced, or partially hydroxylated rutile TiO(2)(110) surfaces. Analysis of the electronic structure reveals that the main contribution to the binding energy is the overlap between the highest occupied molecular orbitals of Au clusters and the Kohn-Sham orbitals localized on the bridging and the in-plane oxygen of the rutile TiO(2)(110) surface. The structure of adsorbed Au(n) differs from that in the gas phase mostly because the cluster wants to maximize this orbital overlap and to increase the number of Au-O bonds. For example, the equilibrium structures of Au(5) and Au(7) are planar in the gas phase, while the adsorbed Au(5) has a distorted two-dimensional structure and the adsorbed Au(7) is three-dimensional. The dissociation of an adsorbed cluster into two adsorbed fragments is endothermic, for all clusters, by at least 0.8 eV. This does not mean that the gas-phase clusters hitting the surface with kinetic energy greater than 0.8 eV will fragment. To place enough energy in the reaction coordinate for fragmentation, the impact kinetic energy needs to be substantially higher than 0.8 eV. We have also calculated the interaction energy between all pairs of Au clusters. These interactions are small except when a Au monomer is coadsorbed with a Au(n) with odd n. In this case the interaction energy is of the order of 0.7 eV and the two clusters interact through the support even when they are fairly far apart. This happens because the adsorption of a Au(n) cluster places electrons in the states of the bottom of the conduction band and these electrons help the Au monomer to bind to the five-coordinated Ti atoms on the surface.