What is the pixel dimensions of the Photoshop document? What is the pixel dimension of the image you are pasting into it? Which is going bad, the image in the original Photoshop document, or the one you are placing into it? Is this a problem with a specific document, or does it happen with everything?
This will not apply if you really are pasting into the target image, but if you are pasting, and these Preference settings are checked (which I think is the default), then it could be that the pixel size of the source image is way too small.
If you are sourcing your images from Google, are you making use of the Size filter? You can go right up to 9000 pixels on the long side with 'Larger than...' It is important that you chose appropriate sizes when introducing new image elements.
There is actually a useful side benefit of searching for large pixel sizes. It gets you past all the watermarked stock images that fill the first several pages, and it is obviously better to work with larger images from the point of view of making selections etc.
This happens to me as well! I notice it most when I take screen shots. If I paste the screen shot into a more simple program like Paint or Powerpoint, the "quality" is preserved. But when I paste into a new Photoshop file it tends to loose quality, by which I mean that text is too blurry to read.
The below Huntington lake map was pasted into Paint. You can easily read all the road names. (I'm not sure if this will transfer well to inserting into a post, but hopefully you can tell the difference). This image is 396KB, 1904x1062pixels, 96dpi.
This Dinkey Creek Road map is 2 screenshots (the road runs over two maps) pasted into a blank document in Photoshop so I could line them up and create a single continuous map of the whole road. The "quality" is so low I can't read any of the road names and can barely distinguish the line pattern types to see what kind of road it is. This image is 413KB, 1252x770pixels, 72dpi.
Here is a close up section of the same Dinkey Creek Rd map. This file is 195KB, 837x588pixels, 72dpi.