Millisecond pulsars are supposed to be old neutron stars. However, they are spinning even more rapidly than newly formed pulsars. Since pulsars slow down as they age, something must have caused these older pulsars to "spin up" and be rotating as fast as they are. What is the mechanism for doing so?
They accrete gas from a disk, fed by either a wind or Roche lobe overflow from their companion. Almost all known millisecond pulsars are in binary systems, but I think some in globular clusters may have been disrupted by three-body encounters, so appear to be isolated.
There are a couple of pieces of observational evidence that support the explanation Jeremy provided. Many millisecond pulsars have been found via x-ray or gamma ray observations, and is interpreted as accretion in a disk on to the surfaces of the pulsars. The falling material speeds up the rotation of the pulsar due to conservation of angular momentum. Pulsars which are in the process of "consuming" the mass of a companion star are often called "black widow pulsars".
Currently, something like 30% of millisecond pulsars are thought to be isolated, with 70% in binary systems. Two systems are known to have planetary mass companions, the most recent having been discovered last year (Transformation of a Star into a Planet in a Millisecond Pulsar Binary). While three body encounters may account for some of the solitary millisecond pulsars known, some millisecond pulsars may completely consume their donor stars. Some authors have argued that one of the millisecond pulsars with planets likely formed as a millisecond pulsar, and formed with a very low magnetic field (Implications of the PSR 1257+12 Planetary System for Isolated Millisecond Pulsars). Since the rate of "spin-down" of a pulsar, that is how quickly its period gets longer, depends on the strength of its magnetic field, a pulsar with a weak magnetic field will stay at its rotation speed for a much longer time.