The size of $|p^n(a)|$ can be very different depending on $a$.
If $a$ is periodic point of 
$p$, then
this sequence will
be bounded. If $a$ is in the domain of attraction of infinity then
$\log|p^n(a)|$ is like $d^n$ where $d$ is the degree.

More precisely, for each polynomial there is a compact set $K(p)$ in the complex plane,
called the filled in Julia set, such that for $a\in K(f)$ your sequence is bounded, while
for $a\not\in K(p)$ it grows like $d^n$. When searching on Google look on "Holomorphic dynamics".

Remark. It is irrelevant for what I wrote above, whether $a$ is an integer or not and whether the coefficients are integer or complex. However, as Joe Silverman suggested in his comment, if the coefficients and $a$ are integers, then $p^n(a)$ are
also integers, and as $K(f)$ may contain only finitely many integers,
the sequence can be bounded only if it is pre-periodic, that is becomes periodic after
the removal of finitely many terms.

EDIT. So for polynomials over integers and integer $a$, the question whether the sequence is bounded can be solved by finitely many arithmetic operations. But this is not completely trivial: one needs an explicit estimate, how many integer points can $K(f)$ contain, or something equivalent to this.

And from the discussion of the history I conclude that the result essentially follows from a [theorem of L. E. Bottcher (early 1900-s)][1] who proved the existence of an analytic function
$\phi(z)\sim z$ near $\infty$ which conjugates the polynomial with $z^d$, that is
$$\phi\circ p(z)=\phi(z)^d.$$
But Bottcher did not investigate the full domain of existence of this function, 
and $\phi$ may not exist
in the whole domain of attraction of $\infty$. The idea to consider $\log|\phi|$ which is well-defined in the whole domain of attraction and can be extended to a subharmonic function in the whole plane
was for the first time published by [Brolin in 1965][2]. Tate apparently had the same idea simultaneously or earlier but did not publish it.


  [1]: https://en.wikipedia.org/wiki/B%C3%B6ttcher%27s_equation
  [2]: https://projecteuclid.org/download/pdf_1/euclid.afm/1485893514