firefox stores it's history/bookmarks and such info in a database (places.sqlite) file in your profile directory. It stores every link it hits by default.
My suggestion is to goto your view history menu, manually delete the history. Then goto your preferences and select the privacy settings that minimize this remembering as much as you can handle. Obviously, selecting never remember history is going to yield the fastest startup times for firefox.
You can double check everything is working by looking at the size of the database files in the profile directory (all end in sqlite). None should be very big after you make these changes.