I claim that the random walk on $T$ is recurrent if $n\leq 2$ and transient if $n \geq 3$. The easiest and most standard way to prove this is to use the comment above by Ian to reduce the problem to an easier problem about Markov Chains on $\Bbb N$. A standard approach to the theory of recurrence and transience can be found starting on page 75 here.
However, I would like to outline a different approach to prove the transience part of the statement for $n \geq 3$. This approach uses harmonic functions and martingales. Namely, we will reduce the problem of proving transience to finding a nonconstant bounded harmonic function on $T$.
Definition: A function $f:T \to \Bbb R$ is harmonic if its value at every node is equal its average value over all neighboring nodes, i.e, $\;f(v)=\frac{1}{n}\sum_{w \sim v} f(w)$.
Lemma: If the random walk on $T$ is recurrent, then every bounded harmonic function from $T \to \Bbb R$ is constant.
Proof: Let $X_n$ denote the random walk on $T$ starting from some arbitrary base vertex $x_0$, and let $f:T \to \Bbb R$ be some bounded harmonic function. Then $f(X_n)$ is a bounded martingale (this is straightforward). Let $x \in T$ be an arbitrary vertex, and let $\tau_x$ denote the first hitting time of $x$ by $X_n$. By recurrence $\tau_x<\infty$. Since bounded martingales are uniformly integrable, the optional stopping theorem tells us that $f(x) = \Bbb E[f(X_{\tau_x})]=\Bbb E[f(X_0)] = f(x_0)$. Thus $f$ is constant. $\Box$
Proof of Transience for $n \geq 3$: Let $T_3=T$ be our tree of degree $3$. Let $B_2$ denote an infinite binary tree. Then $B_2$ embeds into $T_3$ in a straightforward way, so it suffices to show the existence of a nonconstant bounded harmonic function from $B_2 \to \Bbb R$. For $v \in B_2$ we define $|v|$ to be the height of $v$ below the root vertex. We also define $\sigma(v) \in \{-1,1\}$ to be the sign of $v$, which is defined to be $1$ if $v$ is on the left half of $B_2$ and $-1$ if $v$ is on the right half of $B_2$ (the root vertex has no sign). Then we define our nonconstant bounded harmonic function from $B_2 \to [-1,1]$ by sending $v \mapsto \sigma(v) \cdot (1-2^{-|v|})$. It is easily checked that this function is harmonic. This gives transience on $T_3$, and by an easy embedding argument and induction we get transience on $T_n$ for $n \geq 3$. $\Box$
