What is the average pathlength and probability to randomly traverse any given graph?

It's difficult to claim an average because there exist many possible infinite length paths that never reach $B$. You may want instead to calculate the probability that you have reached $B$ after $n$ steps.

@draks ... is on to something, but if you're going to determine the probably that you have "seen" node $B$ after $n$ steps, then you definitely need to include the probability as weights in the adjacency matrix.

Question: For the given graph $G$, what is the probability of having seen node $B$ at the $n^{th}$ step?

Answer: Let us write the adjacency matrix of $G$ weighted with edge probabilities as $$M = \begin{bmatrix} 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & 0 & 0 & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{1}{3} & 0 & 0 & 0 \\ \frac{1}{5} & \frac{1}{5} & 0 & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & 0 & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & 0 & 0 & \frac{1}{3} & 0 \\ 0 & \frac{1}{4} & \frac{1}{4} & 0 & 0 & \frac{1}{4} & 0 & \frac{1}{4} \\ 0 & 0 & \frac{1}{4} & 0 & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} \\ 0 & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ \end{bmatrix}$$

Let $N$ be the matrix $M$ with the last row and column removed. Then the probability of having seen $B$ at step $n$ is then equal to 1 minus the sum of the first row of $N^{n}$ (because that is the row corresponding to the node we started from $A$).

Here's a pretty picture of how the probability changes as $n$ increases: