Decoherence is studied in an attractive proposal for an actual implementation of a quantum computer based on trapped ions.Emphasis is placed on the decoherence arising from the vibrational motion of the ions, which is compared with that due to spontaneous emission from excited states of the ions. The calculations is made tractable by exploiting the vast difference in time scales between the vibrational excitations and the intra-ionic electronic excitations. Since the latter are several orders of magnitude faster, an adiabatic approximation is used to integrate them out and find the inclusive probability for the electronic state of the ions to evolve as it would in the absence of vibrational coupling, and the ions to evolve into any state whatsoever. The decoherence time is found at zero temperature and for any number of ions N in the computer. Comparison is made with the spontaneous emission decoherence, and the implications for how trap voltages and other parameters should be scaled with N are discussed.