"How did Google find out the other companies were being targeted?"

Google runs data centers, and probably sees a lot more traffic than for its own services. Also, who is to say these companies are not using Google products (Gmail, Docs, etc.)? In other words, I think Google might be in a position to know.