How do I get iTunes to actually PLAY songs at random once shuffle is turned on? I am in my iTunes library (not a playlist) and have "shuffle" turned on (songs, not albums). If I click on "play", it plays the song currently highlighted, then stops (it does not play another song afterwards).

The only way I get it to play several songs is by manually checking the songs I want to be played. Which obviously is the opposite of random shuffling.

Also, when I turn off shuffle, then turn it on again, I don't see any change in the order of songs in the library (whereas when I'm in a playlist, I do see a change in the order).

In all the help forums, I've only found answers to the question of how to turn "shuffle" on. I know that. But how do I get iTunes to play songs randomly 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.