Lehrer describes two different "old" methods, commonly referred to as the equal additions method and the decomposition method. The descriptions I have seen of these methods use the term "borrow" instead of "carry". There is an adaptation that can be applied to either method (but more naturally to the equal additions method) that rewrites the subtraction problem as an addition problem, in which case the term "carry" becomes more appropriate. When this adaptation is applied to the equal additions method, the resulting method is known as the Austrian method, which is described in Steven Alexis Gregory's answer. Since this is not one of the methods Lehrer uses in the introduction to his song, I am slightly puzzled by his use of the term "carry", but perhaps this was common in schools, possibly owing to a tendency to conflate the equal additions and Austrian methods.
The decomposition method is the one commonly taught in American schools today and is identical to the "New Math" method satirized in Lehrer's song. The satire is directed toward the emphasis on "understand[ing] what you're doing" rather than "get[ting] the right answer", manifested in the constant references to place value, the aside about the commutative law, and the generalization to bases other than 10.
The distinction between the equal additions method and the decomposition method is in how one compensates for borrowing. When a ten needs to be borrowed for the ones column, the equal additions method compensates by adding a one to the tens column of the subtrahend, on the principle that $a-b=(a+10)-(b+10)$, whereas the decomposition method compensates by subtracting a one from tens column of the minuend. Lehrer demonstrates both for the problem $342-173$:
if you’re under 35 or went to a private school you say seven from three is six but if you’re over 35 and went to a public school you say eight from four is six, ...
This is consistent with the history described in Susan Ross and Mary Pratt-Cotter. 1997. Subtraction in the United States: An Historical Perspective. Mathematics Educator 8(1), 49-56. They write:
During the early to middle 1900’s, examples could be found where different textbooks used any combination of the three different algorithms for teaching subtraction... All of this was to change. In November 1937, William A. Brownell conducted a study to determine if a “crutch” in the algorithm of subtraction problems was beneficial. The crutch involved marking through numerals from which an amount was borrowed in order to keep track of the different steps when working a problem.
They go on to show that after the end of the 1930s, the decomposition method using the "crutch" became the dominant method taught in American schools. Lehrer's song came out in 1965. The remark about those "under 35" using decomposition, i.e. "seven from three is six", is consistent with Ross and Pratt-Cotter's chronology.
That the New Math method was the decomposition method is not just my perception. Ross and Pratt-Cotter describe this period:
In the 1960’s, the School Mathematics Study Group published a textbook series for the elementary grades, where the focus was on the use of place value. Numbers were written in expanded form and used to explain the subtraction process and algorithm. When subtraction requiring regrouping is first introduced, an abacus is used to illustrate the renaming along with writing the number in expanded form. This process was then very quickly shortened into the algorithm using the crutch. Very little actual change was made in teaching subtraction in spite of the emphasis on place value. The decomposition algorithm was still utilized.
An article that answers one of your other questions is Enzinger, N. 2014. An Investigation of Subtraction Algorithms from the 18th and 19th Centuries. MAA Convergence: Loci. About the origin of the decomposition method, also called "simple borrowing", it says
This algorithm is quite old, dating back to Spain in the thirteenth century, Italy in the Middle Ages, and India even earlier (Smith, 1909). In fact, there is evidence of the decomposition algorithm present in the writings of Rabbi ben Ezra (1140, cited in Smith, 1925).
The text in Figure 8 of the paper, taken from an 1830 book of Daniel Adams is interesting. It describes the decomposition method and uses the term "borrowing", giving an explanation involving place value. It also briefly describes the equal additions method as an alternative.