First of all I needed script for that. Very good one I found on Photo Matt site. Here is a copy:

<?php
/*
By Matt Mullenweg > http://photomatt.net
Inspired by Dan Benjamin > http://hiveware.com/imagerotator.php
Latest version always at:
http://photomatt.net/scripts/randomimage
*/// Make this the relative path to the images, like "../img" or "random/images/".
// If the images are in the same directory, leave it blank.
$folder = ”;
// Space seperated list of extensions, you probably won’t have to change this.
$exts = ‘jpg jpeg png gif’;
$files = array(); $i = -1; // Initialize some variables
if (” == $folder) $folder = ‘./’;
$handle = opendir($folder);
$exts = explode(’ ‘, $exts);
while (false !== ($file = readdir($handle))) {
foreach($exts as $ext) { // for each extension check the extension
if (preg_match(’/\.’.$ext.’$/i’, $file, $test)) { // faster than ereg, case insensitive
$files[] = $file; // it’s good
++$i;
}
}
}
closedir($handle); // We’re not using it anymore
mt_srand((double)microtime()*1000000); // seed for PHP < 4.2
$rand = mt_rand(0, $i); // $i was incremented as we went along
header(’Location: ‘.$folder.$files[$rand]); // Voila!
?>

I saved that as a file: rotate.php.

Then I created folder where I keep all random images (cropped to the size of header image; in my case 806 * 189 px) and above file.
I called it header and placed in images folder of theme I use (MistyLook), so the path looks like that wp-content/themes/MistyLook/img/header.

Finally in style.css file of my theme I changed part of code responsible for header image:

#headerimage {
clear: both;
background: #fff url(img/karkonosze.jpg) no-repeat 0px 0px;

to

#headerimage {
clear: both;
background: #fff url(img/header/rotate.php) no-repeat 0px 0px;

And that’s all :).