First a correction regarding the connection with Chebyshev polynomials. Quoting from Chris Godsil's answer to your earlier question:
Observe that
$$
p_0(A)=I,\quad p_1(A) =A,\quad p_2(A) = A^2-\Delta,
$$
where $\Delta$ is the diagonal matrix of valencies of $X$. If $n\ge3$ we have the recurrence
$$
Ap_n(A) = p_{n+1}(A) +(\Delta-I) p_{n-1}(A).
$$
(I have changed $r$ to $n$ in the quoted text.) For cubic graphs, $\Delta=3I$, which results in the recurrence
$$
p_{n+1}(t)=tp_n(t)−2p_{n−1}(t).
$$
This is related to the recurrence for Chebyshev polynomials by a change of variable,
$$
p_{n+1}(2^{3/2}t)=2^{3/2}tp_n(2^{3/2}t)−2p_{n−1}(2^{3/2}t),
$$
followed by a rescaling,
$$
2^{−(n+1)/2}p_{n+1}(2^{3/2}t)=2t\cdot2^{−n/2}p_n(2^{3/2}t)−2^{−(n−1)/2}p_{n−1}(2^{3/2}t).
$$
Hence $q_n(t):=2^{−n/2}p_n(2^{3/2}t)$ satisfies the Chebyshev recurrence, $q_{n+1}(t)=2tq_n(t)-q_{n-1}(t)$. This can be used to obtain $q_n(t)$ for $n\ge3$. For $n<3$,
$$
q_0(t)=1,\quad q_1(t)=2t,\quad q_2(t)=4t^2-3/2.
$$
The Chebyshev polynomials of the second kind are generated from the same recurrence with the initial conditions
$$
U_0(t)=1,\quad U_1(t)=2t,
$$
which result in
$$
U_2(t)=4t^2-1
$$
rather than $4t^2-3/2$. The appearance of the $3/2$ term $q_2(t)$ can be traced to the occurrence of $\Delta$ rather than $\Delta-I$ in the expression for $p_2(A)$. The recurrence implies that $U_{-1}(t)=0$. As a consequence,
$$
q_n(t)=U_n(t)-\frac{1}{2}U_{n-2}(t)
$$
holds for $n=1$ and $n=2$. By linearity of the recurrence, this extends to all $n\ge1$. It does not hold for $n=0$, however, since $U_{-2}(t)=-1$.
From $p_n(t)=2^{n/2}q_n(2^{-3/2}t)$ it follows that
$$
p_n(t)=2^{n/2}U_n(2^{-3/2}t)-2^{(n-2)/2}U_{n-2}(2^{-3/2}t)
$$
for $n\ge1$. The MathWorld expression you quote then implies that
$$
2^{n/2}U_n(2^{-3/2}t)=\sum_{r=0}^{\lfloor n/2\rfloor}(−2)^r\binom{n−r}{r}t^{n−2r},
$$
and therefore that
$$
p_n(x)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}-\sum_{r=0}^{\lfloor (n-2)/2\rfloor}(-2)^r\binom{n-2-r}{r}x^{n-2-2r}.
$$
Shifting the summation index in the second sum in the expression above and bringing the minus sign inside gives
$$
p_n(x)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}+\sum_{r=1}^{\lfloor n/2\rfloor}(-1)(-2)^{r-1}\binom{n-1-r}{r-1}x^{n-2r},
$$
which is a useful form for the purpose of interpretation.
Original answer: This formula can be understood in terms of the process of iteratively carrying out the recurrence in Chris Godsil's answer, which gives rise to sums of products of $A$ and $\Delta$. Define
$$
\Delta':=\begin{cases}\Delta & \text{if first factor in the product}\\ \Delta-I & \text{otherwise.}\end{cases}$$
Note that for cubic graphs,
$$
\Delta':=\begin{cases}3I& \text{if first factor in the product}\\ 2I & \text{otherwise.}\end{cases}$$
Starting with $p_1(A)=A$, $p_{n+1}(A)$ is obtained from $p_n(A)$ by
- appending a factor of $A$ to every term in the sum;
- for any term in the resulting sum that ends with two consecutive factors of $A$, subtracting the product that results from replacing these final two factors of $A$ with a single factor of $\Delta'$.
Carrying this out in the case $n=1$, Step 1 gives $AA$ and Step 2 gives $AA-\Delta'$, with the result $$p_2(A)=AA-\Delta'.$$ Then for $n=2$, Step 1 gives $AAA-\Delta'A$, and Step 2 gives $-A\Delta'$, with the result $$p_3(A)=AAA-\Delta'A-A\Delta'.$$ One more time: Step 1 gives $AAAA-\Delta'AA-A\Delta'A$ and Step 2 gives $-AA\Delta'+\Delta'\Delta'$, with the result $$p_4(A)=AAAA-\Delta'AA-A\Delta'A-AA\Delta'+\Delta'\Delta'.$$
It should be clear that the result of the recurrence is that $p_n(A)$ is a sum with the following characteristics:
- every string of weight $n$ consisting of $A$ and $\Delta'$ occurs exactly once; here weight is computed as $$(\text{number of $A$s})+2\cdot(\text{number of $\Delta'$s})$$
since each $\Delta'$ replaces two $A$s;
- the sign equals $$(-1)^\text{number of $\Delta'$s}.$$
The sum may have anywhere between $0$ and $\lfloor n/2\rfloor$ $\Delta'$s. A string containing $r$ $\Delta'$s consists of $n-r$ symbols since each $\Delta'$ has weight $2$. Hence there are $\binom{n-r}{r}$ strings with $r$ $\Delta'$s.
These observations can be related to the expression for $p_n(x)$ given above. We start by incorrectly replacing every occurrence of $\Delta'$ in each string with $2I$. This gives the incorrect formula
$$
p_n(A)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}A^{n-2r}.
$$
The formula is wrong because the first $\Delta'$ in a string should have been replaced with $3I$ instead of $2I$ if that $\Delta'$ were the first letter of the string. We therefore correct our expression by adding $(-1)\cdot(-2)^{r-1}A^{n-2r}$ for each string with $r$ $\Delta'$s in which $\Delta'$ is the first letter. There are $\binom{n-1-r}{r}$ such strings. As a result, the correct expression is
$$
p_n(A)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}A^{n-2r}+\sum_{r=1}^{\lfloor n/2\rfloor}(-1)\cdot(-2)^{r-1}\binom{n-1-r}{r}A^{n-2r}.
$$
New answer (19 May 2015): The powers of $-1$ suggest that the sum arises from the principle of inclusion-exclusion. In general terms, given a finite set $S$ and a set $T$, the size of the complement of $T$ is given by
$$
\lvert T'\rvert=\lvert S\rvert-\sum_{i=1}^N S_i+\sum_{1\le i<j\le N}S_i\cap S_j-\sum_{1\le i<j<k\le N}S_i\cap S_j\cap S_k+\ldots,
$$
where $S_1$, $S_2$, $\ldots$, $S_N$ are subsets of $S$ whose union is $T$. In your problem, the role of $S$ is played by the set of paths from $a$ to $b$ of length $n$, which we will denote $P(a,b,n,\{\})$; the role of $T$ is played by the subset of $P(a,b,n,\{\})$ consisting of those paths containing at least one reversing step, and the role of $T'$ is played by the subset of $P(a,b,n,\{\})$ consisting of those paths containing no reversing step.
To carry out an inclusion-exclusion calculation, the first step is to choose sets to play the role of $S_i$. A natural choice is to use the sets
$$
P(a,b,n,\{j\})=\text{set of paths from $a$ to $b$ of length $n$ in which step $j$ reverses step $j-1$,}
$$
where $j$ ranges from $2$ to $n$. It is clear that the union of these sets is the set of paths from $a$ to $b$ of length $n$ containing one or more reversing steps. In performing the inclusion-exclusion sum one needs to compute sizes of intersections of two or more sets—intersections like $P(a,b,n,\{j\})\cap P(a,b,n,\{k\})=:P(a,b,n,\{j,k\})$, for example. In this example, the size of the intersection depends on whether $k=j+1$ or $k>j+1$, and this makes the computation a bit involved. It is carried out in this post.
Since the only requirement on the sets $S_i$ is that their union equal $T$, many choices are possible. In this problem, a better choice for the sets to play the role of $S_i$ are the sets
$$
\begin{aligned}
R(a,b,n,\{j\})=\,&\text{set of paths from $a$ to $b$ of length $n$ in which step $j$ reverses step $j-1$ and}\\
&\text{step $j-1$ does not reverse step $j-2$,}
\end{aligned}
$$
where again $j$ ranges from $2$ to $n$. (When $j=2$ we consider the condition that step $1$ not reverse step $0$ to be vacuously true as there is no step $0$.) Again, the union of these sets is the set of all paths from $a$ to $b$ of length $n$ containing one or more reversing steps. This follows from the fact that in any path containing a reversing step, there is a reversing step of least index. Hence if that least index is $j$, then the path is contained in $R(a,b,n,\{j\})$.
Since $R(a,b,n,\{j\})\cap R(a,b,n,\{j+1\})=\emptyset$, we need only consider the case $R(a,b,n,\{j\})\cap R(a,b,n,\{k\})=:R(a,b,n,\{j,k\})$ with $k>j+1$ and, more generally, intersections like $R(a,b,n,\{j_1\})\cap\ldots\cap R(a,b,n,\{j_r\})=:R(a,b,n,\{j_1,\ldots,j_r\})$ in which $\lvert j_k-j_i\rvert\ge2$ for all distinct $i$, $k$ in $\{1,2,\ldots,r\}$. We will assume this condition from now on.
The set $R(a,b,n,\{\})$ of all paths from $a$ to $b$ of length $n$ has size given by the $(a,b)$ element of $A^n$. To handle the case where a reversing step is required at a given position, we need to consider products in which a pair of $A$s has been replaced by $\Delta$ or $\Delta-I$. We use the definition of $\Delta'$ given in the earlier answer. Since a reversal in step $j$ implies that the same vertex is visited after the $(j−2)^\text{nd}$ and $j^\text{th}$ steps, and since if $j>2$ the vertex visited after the $(j-1)^\text{st}$ step cannot be the same as that visited immediately prior to the $(j-2)^\text{nd}$ step, $\lvert R(a,b,n,\{j\})\rvert$ is the $(a,b)$ element of
$$
A^{j−2}\Delta'A^{n−j}=
\begin{cases}(3I)A^{n-2}=3A^{n-2} & \text{if $j=2$,}\\
A^{j−2}(2I)A^{n−j}=2A^{n−2} & \text{if $j>2$.}
\end{cases}
$$
In other words, the two factors of $A$ at positions $j-1$ and $j$ in $A^n$ have been replaced with $\Delta'$. By the same argument, $\lvert R(a,b,n,\{j_1,\ldots,j_r\})\rvert$ is the $(a,b)$ element of the product in which the two $A$s at each of the pairs of positions $(j_1-1, j_1)$, $\ldots$, $(j_r-1,j_r)$ in the product $A^n$ get replaced with $\Delta'$. Because of the condition $\lvert j_k-j_i\rvert\ge2$ for distinct $i$, $k$, these replacements never occur in overlapping positions and can therefore be made independently of one another. Denote by $D_r$ the set of subsets of $\{2,3,\ldots,n\}$ of size $r$ in which this "difference-$2$" condition holds.
By the principle of inclusion-exclusion, the number of paths from $a$ to $b$ of length $n$ with no reversing steps is given by
$$
\sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\sum_{A\in D_r}\lvert R(a,b,n,A)\rvert.
$$
This is equal to the $(a,b)$ element of
$$
\sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\sum_{A\in D_r}[2+\mathbf{1}_A(2)]2^{r-1}A^{n-2r}=\sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\left[\sum_{A\in D_r}2^rA^{n-2r}+\sum_{A\in D_r,2\in A}2^{r-1}A^{n-2r}\right],
$$
where $\mathbf{1}_A(x)$ is the indicator function whose value is $1$ if $x\in A$ and $0$ if $x\notin A$. There is a one-to-one correspondence between elements of $D_r$ and strings containing $n-2r$ $A$s and $r$ $\Delta'$s. There is a one-to-one correspondence between elements of $D_r$ containing $s$ and strings containing $n-2r$ $A$s and $r$ $\Delta'$s such that the initial element of the string is a $\Delta'$. This implies that there are $\binom{n-r}{r}$ elements in $D_r$ and $\binom{n-1-r}{r-1}$ elements in $D_r$ that contain $2$. The sum given in my earlier answer results.
