This has already been answered but I would like to add some points which I hope might be of interest. The clearest expression is, in my opinion, in the general setting of a complete metric space $M$ with a base point $x_0$ and radius $1$. One then defines the Banach space $F$ consisting of the Lipschitz functions which respect the base, i.e., map $x_0$ onto $0$, with the natural norm. Then one can embed the metric space isometrically into a Banach space $E$ with the universal property that every Lipschitz map on $M$ into a Banach space $G$ which respects the base lifts to a unique linear operator on $E$ with the same norm. If one takes $G$ to be one-dimensional, then one sees that the dual of $E$ is the space of Lipschitz functions above. Now the unit ball of the latter has a natural compact topology (pointwise or uniform convergence) and so, by standard duality theory, is a dual space. One can then turn this reasoning on its head and define $E$ to be its predual.
One can see this more clearly if one uses a little terminology from category theory. If we map a Banach onto its unit ball, then we define a functor from the category of Banach spaces (with linear contractions as morphisms) into that of pointed metric spaces with base-point preserving Lipschitz functions, as above, then what we have constructed is just an adjoint functor. That is, the Arens-Eells space can be interpreted as a Free-functor and $AE(X)$ is a free object over $X$.
This is perhaps not really a concrete construction, but it follows from the existence that the space is just the so-called free vector space over $M$ (as a pointed set), completed under a suitable norm (basically the observation of Nik Weaver above). On the other end of the concrete-abstract spectrum, the existence of such an object (often called the free Banach space over $M$) can be deduced from the Freyd adjoint theorem.