http://www.magentocommerce.com/boards/v/viewthread/232826/#t331309
nicely describes how to sort products randomly in Magento categories.
If you override the model and block by local code instead of editing
the core code, you'll have a upgrade-proof version of this.