What receiver are you using?
There are several receivers out there that have HDMI inputs, but those HDMI inputs are limited to the same audio signals as a S/PDIF connection. In other words, the HDMI inputs can only accept Dolby Digital (EX), DTS (-ES) and 2-channel PCM signals.
Double check that your receiver can actually accept multi-channel PCM via HDMI first.
It's sad and frustrating.
Some receivers are nothing more than HDMI switches and do not process the signal at all. Some process the video, but not the audio at all. Some are limited to S/PDIF format audio (like I mentioned). Some handle multi-channel PCM audio at 5.1 channels. Some handle multi-channel PCM audio at up to 7.1 channels. And some can accept any audio format, including the new "HD Audio" formats.
Too many possibilities, but that's the sad reality.
So first, make sure your receiver is actually capable of accepting at least 5.1 PCM audio via HDMI. Then, go into the PS3's "Sound" settings tab and select to set it up manually. Chose HDMI, then go through the list and put a check mark beside all of the compatible formats. Finally, under the "Video" settings tab, make sure that HDMI audio is set to output PCM.