We use the identities
$$\tag 1\operatorname{adj}(A)\cdot A=\det A \cdot I_n$$
and $$\tag 2\operatorname{adj}(AB)=\operatorname{adj}(B)\cdot \operatorname{adj}(A).$$
We have by (1)
$$\operatorname{adj}(\operatorname{adj}(A)\cdot A)=(\det A)^{n-1}\cdot I_n$$
and using (2)
$$\operatorname{adj}(A)\cdot \operatorname{adj}(\operatorname{adj}(A))=(\det A)^{n-1}I_n.$$
Multiplying by $A$ we get
$$\det A \cdot I_n \cdot \operatorname{adj}(\operatorname{adj}(A))=(\det A)^{n-1}\cdot A.$$
If $\det A\neq 0$, we get the wanted equality, otherwise it's clear if $n\geq 2$.
Here's an explanation for three dimensional space ($3 \times 3$ matrices). That's the space I live in, so it's the one in which my intuition works best :-).
Suppose we have a $3 \times 3$ matrix $\mathbf{M}$. Let's think about the mapping $\mathbf{y} = f(\mathbf{x}) = \mathbf{M}\mathbf{x}$. The matrix $\mathbf{M}$ is invertible iff this mapping is invertible. In that case, given $\mathbf{y}$, we can compute the corresponding $\mathbf{x}$ as $\mathbf{x} = \mathbf{M}^{-1}\mathbf{y}$.
Let $\mathbf{u}$, $\mathbf{v}$, $\mathbf{w}$ be 3D vectors that form the columns of $\mathbf{M}$. We know that $\det{\mathbf{M}} = \mathbf{u} \cdot (\mathbf{v} \times \mathbf{w})$, which is the volume of the parallelipiped having $\mathbf{u}$, $\mathbf{v}$, $\mathbf{w}$ as its edges.
Now let's consider the effect of the mapping $f$ on the "basic cube" whose edges are the three axis vectors $\mathbf{i}$, $\mathbf{j}$, $\mathbf{k}$. You can check that $f(\mathbf{i}) = \mathbf{u}$, $f(\mathbf{j}) = \mathbf{v}$, and $f(\mathbf{k}) = \mathbf{w}$. So the mapping $f$ deforms (shears, scales) the basic cube, turning it into the parallelipiped with sides $\mathbf{u}$, $\mathbf{v}$, $\mathbf{w}$.
Since the determinant of $\mathbf{M}$ gives the volume of this parallelipiped, it measures the "volume scaling" effect of the mapping $f$. In particular, if $\det{\mathbf{M}} = 0$, this means that the mapping $f$ squashes the basic cube into something flat, with zero volume, like a planar shape, or maybe even a line. A "squash-to-flat" deformation like this can't possibly be invertible because it's not one-to-one --- several points of the cube will get "squashed" onto the same point of the deformed shape. So, the mapping $f$ (or the matrix $\mathbf{M}$) is invertible if and only if it has no squash-to-flat effect, which is the case if and only if the determinant is non-zero.
Best Answer
There is a nice short explanation. You probably know that the determinant of any matrix can be expanded row or column-wise using the minors:
$$\det A=\sum_{i=1}^n a_{ij}(-1)^{i+j}\det A(i\mid j)$$
or
$$\det A=\sum_{j=1}^n a_{ij}(-1)^{i+j}\det A(i\mid j)$$
for any $j$ (resp. $i$) or your liking where we obtain $A(i\mid j)$ by striking out the $i$-th row and the $j$-th column.
We define the coefficients of the adjoint $\hat A$ by $$(\hat A)_{ij}=(-1)^{{i+j}}\det A(j\mid i)$$
Now, upon matrix multiplication, we have
$$(A\cdot\hat A)_{k\ell}=\sum_{i=1}^n (-1)^{i+\ell}a_{ki} \det A(\ell\mid i)$$
If $k=\ell$, then $$(A\cdot \hat A)_{\ell\ell}=\sum_{i=1}^n(-1)^{i+\ell}a_{\ell i}\det A(\ell \mid i)=\det A$$ since we're expanding the determinant through the $\ell$-th row.
If $k\neq \ell$
$$(A\cdot\hat A)_{k\ell}=\sum_{i=1}^n (-1)^{i+\ell}a_{ki} \det A(\ell\mid i)=0$$
for it is the expansion of the determinant of the matrix $A^{k\ell}$ defined by $$(A^{k\ell})=\begin{cases} a_{ij} \text{ if }i\neq \ell\\a_{kj}\text{ if }i=\ell\end{cases}$$ which has two equal rows.