They work by determining a base frequency of a voice and then measure the spoken words in terms of variation from that frequency. Then, the synthesized playback is done by generating the base frequency and varying it according to the measurements. For effects like Frampton's, the playback varies a musical tone (such as guitar chords) instead of generating & using the base frequency.
Development of the Vocoder began surprisingly early--1928. Bell Lab engineer Homer Dudley created the vocoder as a way of encrypting speech for secure radio transmission and compressing speech for transmission over telephone lines.
More precisely, a Vocoder is the component that analyzes speech and a Voder (Voice Operating Demonstrator) is the component that recreates it. The early voders were manual filters (requiring a trained operator) consisting of consoles with fifteen touch-sensitive keys and a foot pedal.
Voder operator in 1939 and as demonstrated at the 1939 World's Fair:
A sound sample from Dudley's 1939 Voder, with introduction (170k au file)
Werner Meyer-Eppler, then the director of Phonetics at Bonn University, recognised the relevance of the machines to electronic music after Dudley visited the University in 1948, and used the vocoder as a basis for his future writings which in turn became the inspiration for the German "Electronische Musik" movement.