I think it might be more intuitive this way:
Let $A \colon V \rightarrow V $ be a linear operator. Let $e = \{e_1,\ldots , e_n\}$ and $f = \{f_1,\ldots , f_n\}$ be bases for $V$. Let $[A]_e$ and $[A]_{f}$ be the matrices of the linear operator $A$ in the given respective bases. Then there exists an invertible matrix $C$ such that $[A]_f = C^{-1} [A]_e C$.
Let $P_A (\lambda)$ represent the characteristic polynomial. Then
$$P_{[A]_f }(\lambda) = \textrm{det } \left( {[A]_f \space - \lambda I}\right) = \textrm{det } \left( C^{-1} [A]_e C \space - \lambda I\right) = \textrm{det }\left( C^{-1} [A]_e C \space - \lambda C^{-1}C\right)$$
Now if we factor out $C$ then factor out $C^{-1}$ we get:
$$\textrm{det } \left( C^{-1} ([A]_e \space - \lambda I) C\right) = \textrm{det } C^{-1} \cdot P_{[A]_e }(\lambda) \cdot \textrm{det} \space C = \textrm{det } C^{-1} \cdot \textrm{det} \space C \cdot P_{[A]_e }(\lambda) \\= \textrm{det } C^{-1}C\cdot \chi_{[A]_e }(\lambda) = P_{[A]_e }(\lambda) $$
In other words, we have shown that $$P_{[A]_f }(\lambda) = P_{[A]_e }(\lambda) $$