When you click the "Save Selection to Quick Part Gallery" item, the dialog includes a box for "Save in". You can select any template that's currently in use, including Normal.dotm and Building Blocks.dotx. When you click OK, the building block is saved in whichever template is shown in that box.
After saving the building block, when you close Word, you should be prompted to save the template by a message like this one:
If you didn't see the message, or if you clicked Don't Save, then the change probably wasn't saved.
If you're saving building blocks in Normal.dotm, you should go to File > Options > Advanced > Save and check the box for "Prompt before saving Normal template" to make sure the message shows up. It's a good idea to keep this checked anyway, so you're notified of any attempt to change Normal.dotm, both intentional and not.
Another thing you can do is look at the Building Blocks Organizer (that's also on the Quick Parts button's menu) to see whether the building block you think you saved is really in the place you expected.
There's one more possibility, although not too common. In some company networks, a misguided IT department may forcibly overwrite every user's Normal.dotm template during login, in an attempt to prevent use of unauthorized styles. Check the date of the file, which you'll usually find in %appdata%\Microsoft\Templates, to see whether it matches the date/time when you saved the building block in that template.
