The decoherence of an anharmonic oscillator in a thermal harmonic bath is examined via a semiclassical approach. A computational strategy is presented and exploited to calculate the time dependence of the purity and the decay of individual matrix elements in the energy representation for a variety of initial states. The time dependence of the decoherence is found to depend on the temperature of the bath, the coupling strength, the initial state of the oscillator, and the choice of quantity measuring the decoherence. Recurrences in the purity and in the off-diagonal matrix elements are observed, as well as the collapse of these matrix elements to the diagonal, providing evidence for the retention of quantum coherence for time scales longer than that indicated by the purity. The results are used to analyze the utility of the Caldeira-Leggett and Redfield models of decoherence and to assess the dependence of dephasing rates on the degree of structure in phase space. In several cases we find that the dephasing dynamics can be described as an initial Zeno-effect regime, followed by a Caldeira-Leggett region, followed by recurrences. (C) 2004 American Institute of Physics.