How do I get iTunes to actually PLAY songs at random once shuffle is turned on?
When iTunes shuffles through a playlist, library, or other list, it only will shuffle among items for which the "checkbox" column is checked. By default, this would include all the items in your library; only if you uncheck the box for a song would that remove it from the list of songs to shuffle.

It sounds as though your library is set up with all the songs unchecked. If no songs are checked to be included in shuffle, one gets the behavior you describe. The solution is to go to your library and make sure all your items are checked, not unchecked.