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.