I was wanting to add this feature for quite some long time now.There are many ways .I will try to jot down all them I have come across
Go to http://www.linkwithin.com/learn?ref=widget and follow the steps given there.
You can even configure the numbers of related posts you want to show up.
I have used this method in my blog.The best part is it will show random post and does not depend on label.
When you add this there is no separation between the post and related post widget . To add a separation
Find the below line in Edit HTML in 'Design' Section -
Add below lines after you find the above
Go to the link http://www.newbloggingtipz.com/2009/04/add-related-posts-below-every-blogger.html and follow the steps.
This is how the related post below your post will look like.
But then it will not be displayed in the home page and will group similar labels together
Go to link
But this one also groups all the posts with same label as the current post.
This is how it will look.
Again same disadvantage as the second method