Suponiendo que la tabla de las imágenes se llama imagenes y contiene un campo Id que almacena valores de Id continuos (1,2,3,4,5...) y el campo Ruta almacena la URL de cada imagen, entonces pones:
Código PHP:
$host='Host del servidor mysql';
$user='Nombre usuario del servidor mysql';
$password='Contraseña del usuario del servidor mysql';
$con=mysql_connect($host,$user,$password)
mysql_select_db('imagenes',$con);
$SQL="SELECT Id FROM imagenes";
$rst=mysql_query($SQL);
$maxid=mysql_num_rows($rst);
$Idimagen=rand (1, $maxid);
$SQL="SELECT Id,Ruta FROM imagenes WHERE Id=$Idimagen";
$rst=mysql_query($SQL);
$row=mysql_fetch_array($rst);
$ruta=$row['Ruta'];
mysql_free_result($rst);
echo '<img href="$ruta">';
mysql_close();