Add the clause "ORDER BY rand()" to your MySQL query?
Closer to the SQL standard; extract all the results into an array, then use PHP's shuffle() function:
$query="select...";
$result=mysql_query...
$records=array();
while($record=mysql_fetch_array($result))
{ $records[]=$record;
}
shuffle($records);