In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a 3x3x3 Rubik's cube, starting in an arbitrary configuration, can strictly be solved in at most 20 Singmaster moves (under the face-turn metric) from Rubik's Cube move group $(G, *)$, where * is the concatenation operation (summarized here: http://en.wikipedia.org/wiki/Rubik's_Cube_group ). In 2011, Erik Demaine et. al. ( http://arxiv.org/abs/1106.5736v1 ) showed that any (n x n x n) Rubik's cube can optimally be solved in $\Theta (\frac{n^2}{Log(n)})$ steps, also under the face-turn metric.
Say we restrict ourselves to the simpler quarter-turn metric (only allowing for 90 degree rotations), and set up the following scenario:
We hand a (n x n x n) Rubik's cube to a robot, and program the robot to execute an random set of 90 degree Singmaster moves in $G$, then stop when the cube is solved. We know that the number of total cube states for a 3x3x3 cube is: $||G|| = (2^{27}*3^{14}*5^3*7^2*11) = 43,252,003,274,489,856,000$ (Turner and Gold 1985, Schonert), and we can therefore use the negative binomial distribution calculate the mean number of random system states we need to sample to find a "finished" cube (call this value $S_3$ for the 3x3x3 cube and $S_n$ for the n x n x n cube). However, the robot is performing random quarter-turn moves, not necessarily randomly sampling cube configurations.
What distribution can we expect for the number of random 90 degree Singmaster moves necessary for the robot to complete the cube? I suppose we can calculate an upperbound for the expected mean number of required moves by taking a product of $S_n$ and the mean number of random moves necessary to "mix" the cube (I'm unaware of an estimate for this time), but can we do better? Also, I would guess that the "mixing time" for the cube is much faster than the solution time, making it the case that the initial state of the cube shouldn't matter.
(I'm not entirely opposed to allowing for arbitrary 90 or 180 degree Singmaster moves by the robot, but it just seems simpler to only consider the set of quarter-turn moves.)
Update :: Based on Brendan McKay's answer, which I mostly agree with, I intuitively feel that that the number of steps to find a solution for a (n x n x n) cube via a random walk on the cube's Cayley graph, should be something like $\Theta (||G|| * log (||G||))$. This intuition is coming from the scaling for the expected coverage time for a random walk on an integer lattice.
From: Jonasson, J., Schramm, O. On the cover time of planar graphs. Electronic Communications in Probability 5, pp. 85 - 90 (2000), we have that the cover time for a $d$-dimensional integer lattice $G$ with $n$ vertices scales as: $\Theta(n^2)$ for $d = 1$, $\Theta(n (\log n)^2)$ for $d = 2$, and $\Theta(n \log n)$ for $d \geq 3$. (hat tip to Andreas Rüdinger for his answer to Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice).
For the Cayley graph of a generalized Rubik's cube, it seems like we're in the limit of the sort of connectivity on an integer lattice that yields $\Theta(n \log n)$ covering times. So I suppose, on average, it should take about half this many steps to find the solved cube configuration?
Obviously this is very very sketchy reasoning, and I hesitate to actually write it down.