How did Ruffini discover his method of polynomial division? At that time was it known that polynomial division works similar to integer division?
Polynomial division algorithms were known long before Ruffini's Sopra la determinazione delle radici (1804). For a history of even older numerical division algorithms see Who invented short and long division?
Some authors, see also Victor Katz's History of Mathematics (7.2.3), credit medieval Arabic mathematician al-Samaw'al (1130-1180) for inventing long division, of both polynomials and integers. Al-Samaw'al was first to use tables of coefficients to write and perform calculations with polynomials, he even allowed negative powers. He described a division method underlying the polynomial long division, although his record keeping is more akin to what is now called synthetic division. He also noted the analogy between his way of writing polynomials and the decimal positional notation, and transferred his algorithms to decimal numbers by simply replacing the variable with $10$, so he may well be the first to provide a mathematical justification for a positional division algorithm.
The method for dividing by a linear factor is presented implicitly in Descartes's La Geometrie (1637), where it is used as a part of his algebraic algorithm for drawing tangents to algebraic curves (described in Is there a 'lost calculus'?). A more efficient algorithm of polynomial division, an optimized version of synthetic division, was produced by Jan Hudde in a letter included into 1659 edition of Descartes's La Geometrie, see a description in Suzuki's The Lost Calculus (1637–1670). Hudde was a talented Dutch mathematician who had to abandon mathematics for politics to save Netherlands from Spanish invasion. Ruffini's rule is an adaptation of Hudde's, see Ruffini’s Rule and meaning of division post.
What Ruffini describes generalizes to the modern synthetic division algorithm for polynomials, see Fitzherbert's Ghosts of mathematicians past: Paolo Ruffini. For subsequent generalizations by Budan and Horner see Chabert's History of Algorithms, 7.9. As a method of finding roots, historians trace the Ruffini–Horner scheme to the Chinese mathematician Jia Xian (ca. 1010–ca. 1070), who lived even earlier than al-Samaw'al, see Similarities between Chinese and Arabic Mathematical Writings: (I) Root extraction by Chemla.