It's not truly random, it is pseudo-random, like almost all computer programs.
MPD uses a Mersenne-Twister pseudo-random number generator, seeded from the kernel's random pool.
This is pretty good, better than what most programs use (most programs use the standard C PRNG, which is rather bad), and certainly good enough for random playback.
If you have numbers demonstrating that there are problems with randomness, post it in a bug report.
