Cookies - those of which are not chocolaty, delicious goodness - are tiny, bite sized text files that websites can save to YOUR browser. Cookies can only be read by the same website that saved them to your browser.
The purpose of cookies
Initially, cookies contained small bits of information, such as your language preferences, items in your cart or your name.
Eventually, websites became more creative and started tracking much more data, exceeding cookies' limits, so we started to just save a small ID to the cookie, and all necessary information is kept in the website's database to be identified by that ID.
How cookies are used nowadays
Now to the million dollar question: How are you shown ads on one website based on your searches on another website?
Most websites that show ads, use an ad service (such as Google's) that embed ads on their site. These ads are in reality hosted on the ad provider's site which means that all those ads on all of those websites can read and writes the same cookies because they come from the same provider.
How to eat my cookies
If you are paranoid about your privacy, you can clear your cookies or even completely disable them in your browser's settings.