So how did Data get his cat, Spot? Did Data pick him up on Earth or something?
Strange though it may sound, there does not appear to be any explanation, canonical or otherwise, for Spot's appearance (let alone for changes of breed or gender, as mentioned in the Memory Alpha article referenced in the comments above). One day, ("Data's Day", to be precise :-) ), we just suddenly discovered that Data had a cat, and apparently had had one for some time.
For all we know, Spot predates Data's duty aboard Enterprise-D. Beyond that, we can speculate endlessly -- she might have been Data's own acquisition or that of another crew member who passed away or discovered they were allergic or otherwise couldn't care for her any more, for example.
We simply don't know, and, to judge from the Memory Beta article (which tracks non-canon references), no author has chosen to speculate.
Spot does look a lot like Tasha Yar's cat. Given that she and Data "hooked up" during the episode 'The Naked Now', perhaps he inherited her cat when she died.
It was mentioned somewhere (wish to GOD I could recall where) that the cat from "Data's Day' had contracted feline leukemia and passed away rather suddenly, and that a second cat had been replaced due to attacking a castmember (I do believe it was Michael Dorn!) when seeing him in costume.
Data's Day happens shortly after Data meets Dr. Soong, and it is clear after he returns to the enterprise that he has brought back some of Soong's belongings. My theory is that Spot actually belonged to his father and so he inherited her.