Auto-tune was invented by Antares Audio Technologies, and works as either a plug-in (for RTAS machines, to Auto-tune in real-time) or as a standalone editor. Users select the file they wish to tune, such as a vocal, and then define the target key and scale. The file is processed according to how much tuning you wish -- just a touch, to correct minor pitch, or a lot, to give certain effects (think T-Pain).
This is accomplished by playing with the phase relationships of the individual notes. Since sound is made of waves, manipulating the very small phase differences in the tone of a human voice can work to change the pitch if done with a proprietary formula.
While it works wonders for correcting pitch, the effect use of Auto-tune has become extremely popular. What makes the Auto-tune effect sound so extreme is that it takes minor changes in pitch -- common in singing -- and pulls them dramatically into key without much variation between.
Auto-tune is one of the most frequently-pirated software titles, but watch out for viruses -- faked, downloaded Auto-tune packages are a well-known source of viruses. Only copies that are legitimate will work due to the need for an iLok key.