Whenever I search the internet for something on my laptop, my wife's desktop computer and her cell (connected thru the wifi) see ads for what I was searching for. So my question is does the router store cookies?
No. That's a web browser function.
The shared public IP address of your router is one possible vector.