They are personalised by the "bucket" that data collection companies like Google or Facebook placed you into based on profiling. Browsing and search history is only one of the factors that is taken into account when you are profiled, there are myriad more ways to collect data about you.
And then what ads you see is determined by what advertisers think your "bucket" wants. If you are male in your 20s living in rural USA and advertisers think that males in their 20s living in rural USA are interested in guns, then that's what you will see - even if you never clicked on gun ad or searched for guns on Google.