Una manera bastante simple de mostrar posts aleatorios, por ejemplo en nuestro sidebar es creando un loop con query_posts e indicando que los ordene de manera random. Sería algo así:

<?php query_posts('showposts=10&orderby=rand');    while (have_posts()) : the_post(); ?>
<li><a href="<?php the_permalink() ?"><?php the_title() ?></a></li>
<?php endwhile; ?>
<?php wp_reset_query(); ?>

Con esto obtenemos una lista de 10 posts aleatorios con sus respectivos enlaces. Si queremos que sólo muestre aleatoriamente los posts de cierta categoría podemos además indicarlo en el array, ya sea con el ID  o el slug de la categoría. Algo así:

<?php query_posts('showposts=10&orderby=rand&cat=5');  while  (have_posts()) : the_post(); ?>

Pueden ver algunos otras opciones de query_posts en el Codex de WP y no se olviden de cerrar con wp_reset_query.