Make sure you not running Firefox in (permanent) Private Browsing mode.

• https://support.mozilla.org/kb/Private+Browsing
• Tools > Options > Privacy > Firefox will: "Use custom settings for history"
• Deselect: [ ] "Always use private browsing mode"

If you not using Private Browsing Mode

• Tools > Options > Privacy > History>
• Firefox will: "Use custom settings for history":
• Select: [x] Accept Cookies from sites
  • Accept third party cookies: "From Visited"
• Keep until "They Expire"
• Deselect: [ ] "Clear history when Firefox closes"
• https://support.mozilla.org/kb/Clear+Recent+History

If you use cleanup software like CCleaner then check the settings for the Firefox application.

If you see "(Never) Remember History" then that means that all history and cookie settings are set to the default value (i.e. cookies are enabled).
The "Use custom settings for history" selection allows to see the current history and cookie settings, but selecting this doesn't make any changes to history and cookie settings.
Firefox shows "Use custom settings for history" as an indication that at least one of the history and cookie settings is not the default to make you aware that changes were made.
If all History settings are default then the custom settings are hidden and you see "Firefox will: (Never) Remember History".
"Never Remember History" means that Private Browsing is active and "Always use private browsing mode" gets a check mark.
"Use custom settings for history" stays selected if at least one of the History or Cookie settings is not the default to make you aware that changes from the default setting have been made.

If you do not keep changes after a restart or otherwise have problems with preferences, see:

• http://kb.mozillazine.org/Preferences_not_saved