Note: This assumes your phone has the "+" or "Add" button in the APN settings. If your phone does not have this, look elsewhere.
Also, you obviously need to know the correct APN settings for your carrier.
If you can "Add" an APN but the settings don't get saved / don't stick:
1. Try putting in ONLY the APN name (i.e. Rogers" and the APN sever (i.e. rogers-core-appl1.apn) and hit SAVE.
If this test APN gets saved to your phone, then the problem isn't that the phone isn't saving the APN settings. The problem is actually that the APN settings you are putting in are wrong and the phone / carrier / APN server is rejecting them.
2. Pull up your test / new APN again. You may find that many of the necessary settings have now been pre-populated.
I don't know exactly how this works. I assume the phone queries the APN server to get them.
3. Start changing the settings from their defaults to the recommended settings, one at a time. After each change, hit "Save" and see if the changes stick.
It is likely that at some point in the process, the "new" APN that you created and previously saved will simply disappear from the APN list. This indicates that the last setting you changed was somehow invalid, even if it is the "right" setting according to your carrier.
For example, Petro-Canada Mobility says to set the Mobile Virtual Network Operator (MVNO) type to "None", but doing so will cause the APN profile to not save. Creating a new APN with ONLY "rogers-core-appl1.apn" as the APN will pull the correct MVNO type (IMSI) and MVNO value (302720x98) to the phone automatically and allow the profile to be saved correctly.