Go to Tools>Clear Private Data also make sure in Tools>Options>Privacy you select the appropriate boxes. Those instructions are for Firefox/2.0.0.3
I always prefer to save my searches but ensure my logon password is not known to anyone else. If you want to clear your searches/data/history its up to you but I find it a timesaver.