In addition to the answer from Matt L., I want to emphasize the fact why the comment mentions the polynomial division. Consider to finite-length sequences $h[n]$ and $x[n]$, with length $N$ (one sequence can be zero-padded to length $N$).
Now, look at the convolution of both:
$$y[n]=h[n]*x[n]=\sum_{n'=0}^{N-1}h[n']x[n-n']$$
As an example, consider the two sequences $h[n]=[1, 2, 3]$ and $x[n]=[4, 6, 5]$. Their convolution is (in Matlab)
>> conv([1 2 3], [4 6 5])
ans =
4 14 29 28 15
Now, consider the product of the two polynomials $h(x)=1+2x+3x^2$ and $x(x)=4+6x+5x^2$ (in Mathematica):
Expand[(1 + 2 x + 3 x^2) (4 + 6 x + 5 x^2)]
>>> 4+14 x+29 x^2+28 x^3+15 x^4
As you can see, the coefficients of the polynomial of the product are equal to the values of the convolution of both sequences.
So, now to get $x[n]$ from $y[n]$, you need to perform the polynomial division of $y(x)/h(x)$:
PolynomialQuotient[4 + 14 x + 29 x^2 + 28 x^3 + 15 x^4, (1 + 2*x + 3*x^2), x]
>>> 4+6 x+5 x^2
Hence, the coefficients of the polynomial yield the original sequence.
This technique can be extended to infinite sequences.
To get the connection to the Z-Transform here: The Z-Transform of the finite sequences $x[n]$ and $h[n]$ are given by
$$H(z)=1+2z^{-1}+3z^{-2}\\ X(z)=4+6z^{-1}+5z^{-2}$$
And the Z-Transform of the output $y[n]$ is given by
$$Y(z)=H(z)X(z).$$
Here, you again have the polynomial multiplication. Also, here it becomes even easier to spot, why it also works with infinite sequences: Then both $H(z)$ and $X(z)$ become fractions of polynomials, but the principle of the polynomial multipication remains.