How did the notions of polynomial addition,multiplication and division develop historically?
The fact that this correspondence with the integers exists seems to be of great importance and is not at all obvious that it exists yet I am unable to find anything on its history.
Polynomial arithmetic is implicit in the works of Diophantus and al-Kwarizmi, where it is based on the geometric algebra found in Book II of Euclid's Elements.
It acquired a more modern look with Viete and Descartes, among others. Particularly important is the work of Viete, who in 1591 introduced letters for the coefficients and showed how to factor a polynomial in terms of its roots. This made polynomials more interesting in themselves, rather than being just a part of an equation for the object of interest.
Throughout the 1600's, several books on algebra were written where this shift of focus was developed, and where good notations were found. When Newton's Arithmetica Universalis was published in 1707, the subject looked much like it does today.