This apparently holds true back to at least GNOME 2.12 or before, but more importantly it still holds true for GNOME 3.0. As a former primarily-Windows user, I always kind of expected to be able to change default file association for a particular kind of file in the Right-Click > Open With menu. That, apparently, is only temporary for that particular file open session. And this was always a frustration point for me.
To change it permanently via the GUI, you need to right-click one of the files in question, go to “Properties”, then over to the “Open With” tab.
On the “Open With” tab, choose the appropriate program in question under either “Recommended Applications” or via the “Show other Application” list. Then click the “Set as Default” button. And there you go! Now your file of that extension will open with whatever application you just selected.