By default, even users not logged in to Google will accumulate a search history. To disable this, visit the submitted URL when not logged in to a Google account and scroll down to the “Signed-out Search activity” toggle. Use a browser mode that persists cookies (that is, don’t use incognito mode).
Repeat on each device you browse from.
Here’s the equivalent for YouTube watch history and search history: https://www.youtube.com/feed/history