Técnica #1
<?php
$rand = array('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f');
$color="#".$rand[rand(0,15)].$rand[rand(0,15)].$rand[rand(0,15)].$rand[rand(0,15)].$rand[rand(0,15)].$rand[rand(0,15)];
?>
Luego repite el valor de $color en cualquier lugar que lo necesites. Por ejemplo:
<body style="background: <?php echo $color; ?>;">
Técnica #2
<?php printf( "#%06Xn", mt_rand( 0, 0xFFFFFF )); ?>
También hay una versión de JavaScript.