his plugin ensures that a user will not see the same post twice.
It does this by keeping a list of single posts that the user has seen and then checking that list when redirecting.
Just put this line anywhere in your theme where you want the link to appear.
<?php random_post_link(); ?>
You can specify the text you want on the link like so:
<?php random_post_link('Feeling lucky'); ?>