[1812Overture]

IP address, or if you have any shared accounts you could have a cookie identifying you as the same user. Ads also target connections of people who're interested in a product so you could get the ad from being friends/following someone who watched the videos. The ads will find you.

[crsmith]

Even if FB/Instagram knows my wife and I share an IP address or there were both FB/Instagram and Google cookies on the same browser where I searched for Meow Mix, how would Instagram know my Google/Youtube history?

[1812Overture]

That's easy. The ad network that serves you ads on YouTube also serves ads on Facebook. They have a profile of you that connects your facebook and google accounts.