This solutions seems kind of simple so I'm not sure if it's correct, but since it's 5x5x5, that means there's 125 smaller cubes right? That means that the probability of choosing a specific cube is 1/125. However, since the second cube is really the only one that matters in this case, the probability of choosing a correct second cube will be 6/124.
Of course that doesn't include the edges so it's wrong. If it's a corner piece (4 pieces), it has 3 possible sides. The side pieces have 5 possible sides and there are 80 side pieces. That leaves 45 inside pieces that do have 6 possible sides. So the first cube chosen is gonna make a difference.
P(1st cube is a corner piece) = 4/125
P(1st cube is a side piece) = 80/125
P(1st cube is inside piece) = 45/125
P(2nd cube touches corner piece) = 3/124
P(2nd cube touches side piece) = 5/124
P(2nd cube touches inside piece) = 6/124
Therefore:
P(2nd cube touches first cube) = 4/125*3/124 + 80/125*5/124 + 45/125*6/124
= .044
