You have Firefox set to use automatic private browsing mode. In this mode, history is stored temporarily during your session but is cleared when you exit Firefox. You should be able to confirm when Firefox starts up that it has no history from any previous session, for example, in the Library dialog (Ctrl+Shift+h).

The nice thing about private browsing is that sites work normally. If you want to manage your history settings manually, you can switch from "Never remember history" to "Use custom settings for history" in the Options dialog (Privacy panel) and uncheck "Always use private browsing mode." The trick then is finding a balance of settings that gives you the site functionality you want (for example, if you block all cookies, some sites won't work).