The number of such walks is $2^n$ (the number of vertices of the $n$-cube) times the number of walks that start (and end) at the origin. We may encode such a walk as a word in the letters $1, -1, \dots, n, -n$ where $i$ represents a positive step in the $i$th coordinate direction and $-i$ represents a negative step in the $i$th coordinate direction. The words that encode walks that start and end at the origin are encoded as shuffles of words of the form $i\ -i \ \ i \ -i \ \cdots\ i \ -i$, for $i$ from 1 to $n$. Since for each $i$ there is exactly one word of this form for each even length, the number of shuffles of these words of total length $m$ is the coefficient of $x^m/m!$ in $$\biggl(\sum_{k=0}^\infty \frac{x^{2k}}{(2k)!}\biggr)^{n} = \left(\frac{e^x + e^{-x}}{2}\right)^n. $$ Expanding by the binomial theorem, extracting the coefficient of $x^r/r!$, and multiplying by $2^n$ gives Qiaochu's formula.
Incidentally, if we let $W(n,r)$ be the coefficient of $x^r/r!$ in $\cosh^n x$, so that
$$W(n,r) = \frac{1}{2^n}\sum_{j=0}^n\binom{n}{j} (n-2j)^r,$$ then we have the continued fraction, due originally to L. J. Rogers,
$$
\sum_{r=0}^\infty W(n,r) x^r =
\cfrac{1}{1-
\cfrac{1\cdot nx^2}{ 1-
\cfrac{2(n-1)x^2}{1-
\cfrac{3(n-2)x^2}{\frac{\ddots\strut}
{\displaystyle 1-n\cdot 1 x^2}
}}}}
$$
A combinatorial proof of this formula, using paths that are essentially the same as walks on the $n$-cube, was given by I. P. Goulden and D. M. Jackson,
\textit{Distributions, continued fractions, and the Ehrenfest urn model,}
J. Combin. Theory Ser. A 41 (1986), 21–-31.