You can write the identity in clifford algebra as
$$\nabla^2 A = \nabla \wedge (\nabla \rfloor A) + \nabla \rfloor (\nabla \wedge A)$$
The wedge $\wedge$ has the general meaning like so: if it acts on two vectors, form a plane spanned by the vectors (it is "dual" to the cross product in this way).
The contraction $\rfloor$ is like a dot product when it's between vectors, but it has the general meaning that, if it acts between a vector and a plane, then the plane is "reduced" to a vector orthogonal to the other vector, but still in the original plane.
All well and good, but why is the above identity true, then? Well, in point of fact, there are some missing terms:
$$\nabla^2 A = \nabla \wedge (\nabla \rfloor A) + \nabla \rfloor (\nabla \wedge A) + \nabla \rfloor (\nabla \rfloor A) + \nabla \wedge (\nabla \wedge A)$$
The last two terms don't appear in the identity as usual. Why? Well, the first of them is identically zero: $\nabla \rfloor A$ is the divergence, so $\nabla \rfloor (\nabla \rfloor A)$ is necessarily zero; you cannot contract a vector and a scalar in any meaningful way, and this is part of the definition of the product. (The converse is that you can take a wedge product of a scalar and a vector, and it's just scalar multiplication. You can't double count this operation and still make sense of things.)
So what about the other term, $\nabla \wedge \nabla \wedge A$? It drops due to the equality of mixed partial derivatives. Write out $(\nabla \wedge \nabla)$ in terms of a basis:
$$\nabla \wedge \nabla = (e^x \wedge e^y) (\partial_x \partial_y - \partial_y \partial_x) + \ldots$$
You can see that all these terms drop out; the wedge product is antisymmetric (like the cross), so all these partial derivatives group together this way.
The net result is that the Laplacian of a vector field is also a vector field, which in itself is pretty handy, as it makes the Laplacian appear "scalar" in its behavior.
Edit: now why does the identity look the way it does in the first place? Again, clifford algebra helps. You can take the "gradient" of a vector field, actually. In clifford algebra, it's just written
$$\nabla A = \nabla \rfloor A + \nabla \wedge A$$
Yes, this is a scalar and...something not quite a vector, but pretty close. Having $\nabla$ work on this again produces the four-term expansion of the Laplacian I gave earlier, and all that remains to prove is that two of those terms are zero.
So it's just the same basic rules of distributing multiplication over addition that you've been familiar with since grade school.