Okay, from what I can tell, the big random playlist function is in Plugins.
From the home screen, go Plugins -> Applications -> random_folder_advance_config.
Start it and hit "Generate Folder List".
When that's done, go down one to "Edit List".
Down and Up navigate the list, Right button or Main button clears an entry, holding down the Main button activates the context menu, and Left-Button exits Edit mode.
After exiting Edit mode, it will ask you to confirm or ignore changes.
After that, scroll down to "Play Shuffled".
EDIT:Apparently 'shuffled' means it randomizes the list of folders, and plays everything in a folder before moving on to another random folder, rather than playing random songs.
More details here:http://www.rockbox.o...mFolderAdvanceConfig
What I would do is generate a giant M3U playlist of what's on your player (most media players like WMP should be able to do that), load that into your Rockbox Playlist folder, and select "Shuffle" from the "Playback Settings" menu.