What did Newton himself do, so that the "Newton polygon" method is named after him?
The Newton polygon and Newton's method are closely related. The following theorem was first proven by Puiseux:
if $K$ is an algebraically closed field of characteristic zero, then the field of Puiseux series over $K$ is the algebraic closure of the field of formal Laurent series over $K$
However according to Wikipedia
This property was implicit in Newton's use of the Newton polygon as early as 1671 and therefore known either as Puiseux's theorem or as the Newton–Puiseux theorem.
A place where this is illustrated in more detail is "A history of algorithms: from the pebble to the microchip" By Jean-Luc Chabert, Évelyne Barbin, page 191. I will quote the first paragraph
Immediately following his description of his numerical method for solving equations, Newton used the same principle to show how to obtain algebraic solutions of equations. He explains how the method of successive linear approximations can be adapted by using a ruler and "small parallelograms", the first version of what is called Newton's polygon. The method was applied in a more general case later, by Puiseux in 1850, both in considering multiple branches and in considering functions of a complex variable
Then it explains Newton's approach in detail. You can follow the references given there. And then we know the story that this nice tool is now used for the understanding of polynomials over local fields even tough originally the local field was the field of formal Laurent series.
here are some references:
"Plane Algebraic Curves" by Brieskorn and Knorrer, around page 370.
"Plane Algebraic Curves" by Fischer, Appendix 4.
is an article from The College Mathematics Journal about the Newton polygon as developed by Newton.
I especially recommend the first reference because it has a wealth of pictures.
(However, it is a monster of a book.)
If memory serves correct the history of Newton's polygon and Puiseaux series has some subtleties, so be a bit wary of secondary historical sources. Histories of mathematics are bursting at the seams with romanticized legends, so it is always best to consult primary sources if you wish to know the real history. The following note from Chrystal's Algebra may serve as a helpful entry into the primary literature.
Historical Note. - As has already been remarked, the fundamental idea of the reversion of series, and of the expansion of the roots of algebraical or other equations in power-series originated with Newton. His famous" Parallelogram" is first mentioned in the second letter to Oldenburg; but is more fully explained in the Geometria Analytica (see Horsley's edition of Newton's Works, t. i., p. 398). The method was well understood by Newton's followers, Stirling and Taylor; but seems to have been lost sight of in England after their time. It was much used (in a modified form of De Gua's) by Cramer in his well-known Analyse dea Lignes Courbea Algebriques (1750). Lagrange gave a complete analytical form to Newton's method in his "Memoire sur l'Usage des Fractions Continues," Nouv. Mem. d. l'Ac. roy. d. Sciences d. Berlin (1776). (See OEuvres de Lagrange, t. iv.)
Notwithstanding its great utility, the method was everywhere all but forgotten in the early part of this century, as has been pointed out by De Morgan in an interesting account of it given in the Cambridge Philosophical Transactions, vol.ix. (1855).
The idea of demonstrating, a priori, the possibility of expansions such as the reversion-formulae of S.18 originated with Cauchy; and to him, in effect, are due the methods employed in SS.18 and 19. See his memoirs on the Integration of Partial Differential Equations, on the Calculus of Limits, and on the Nature and Properties of the Roots of an Equation which contains a Variable Parameter, Exercices d'Analyse et de Physique Mathematique, t. i. (1840), p. 327; t. ii. (1841), pp. 41, 109. The form of the demonstrations given in SS. 18, 19 has been borrowed partly from Thomae, El. Theorie der Analytischen Functionen einer Complexen Veranderlichen (Halle, 1880), p. 107; partly from Stolz, Allgemeine Arithmetik, I. Th. (Leipzig, 1885), p. 296.
The Parallelogram of Newton was used for the theoretical purpose of establishing the expansibility of the branches of an algebraic function by Puiseaux in his Classical Memoir on the Algebraic Functions (Liouv. Math. Jour., 1850). Puiseaux and Briot and Bouquet (Theorie des Fonctions Elliptiques (1875), p. 19) use Cauchy's Theorem regarding the number of the roots of an algebraic equation in a given contour; and thus infer the continuity of the roots. The demonstration given in S.21 depends upon the proof, a priori, of the possibility of an expansion in a power-series; and in this respect follows the original idea of Newton.
The reader who desires to pursue the subject further may consult Durege, Elemente der Theorie der Functionen einer Complexen Veranderlichen Grosse, for a good introduction to this great branch of modern function-theory.
The applications are very numerous, for example, to the finding of curvatures and curves of closest contact, and to curve-tracing generally. A number of beautiful examples will be found in that much-to.be-recommended text-book, Frost's Curve Tracing. -- G. Chrystal: Algebra, Part II, p.370
This was intended to be a comment on Bill Dubuque's answer, but I apparently don't yet have enough reputation points to comment, and in any event this is probably too long to appear as a comment.
Given Chrystal's intended audience, I'm surprised that he didn't mention Talbot's 1860 English translation and extensive commentary of Newton's Enumeration Linearum Tertii Ordinis. In Talbot's work, which is freely available on the internet, see the sections On the Analytical Parallelogram (pp. 88-104) and Examples (pp. 104-112). By the way, whoever scanned the book for google wasn't paying attention when the lengthy list of figures at the end of the book were being scanned, so I'm also giving the University of Michigan Historical Math Collection version, which has those figures correctly scanned.
Sir Isaac Newton's Enumeration of Lines of the Third Order, Generation of Curves by Shadows, Organic Description of Curves, and Construction of Equations by Curves, Translated from the Latin, with notes and examples, by C.R.M. Talbot, 1860.