How to embed screenshots properly?

As the other answers have already made clear, a pixmap graphics is, in general, not very well scalable: You just can't get more "senseful" pixels.

Nevertheless, despite their much lower resolution, screen shots can look relatively well (that is, readable) on the printout, if prepared accordingly. The following is a somewhat loose list of recommendations that work for me:

1. Take the screen shot at the maximum possible resolution. For screen shots of dialog windows, as in your case, it is often a good idea to increase the standard font size in the system settings, so that the pixmap of the dialog window becomes actually bigger.

2. Always use a lossless file format for your screen shots, such as GIF or PNG (the latter being natively supported by pdflatex). Never, ever use JPG for a screen shot!

3. Scale the image only by whole number factors (reciprocals of whole numbers if scaling down). If scaling by a factor of 2, for instance, the scaling algorithm can just double each discrete pixel, so the overall appearance remains the same. If, however, you scale by a factor of 1.1, the algorithm has to somehow make up 11 pixels out of ten, which leads to a blurred appearance.

   A consequence is: Do not scale to \columnwidh or \textwidth, as it would be pure coincidence if that results in a whole number scaling factor. Typeset the image centered and then scale it by factors of 2,3,4,... until you get something that "almost fills" the available space.

4. If, for whatever reason, you have to scale by a rational number: Do not let pdflatex do it; use a good imaging software instead. If you scale by rational factors, the quality of the result depends a lot on the scaling algorithm, which has to take the kind and structure of the image into account. It has to work differently for photos than for screen shots. The algorithm used by pdflatex seems to be optimized for photo scaling.

Just use pdflatex and \includegraphics with an appropriate scaling parameter. That's all.

You can't get anything better than this: your final PDF file will include the original PNG file as is, and the PDF viewer will do its best to scale it appropriately for screen and printer (depending on screen resolution, zoom settings, etc.).

It will look a bit fuzzy on screen in almost all cases, and it is unavoidable (regardless of whether you use a scaling parameter in \includegraphics or not). You can't force the user to choose a zoom level that happens to map 1 pixel in your screenshot to 1 pixel on screen. The whole point of a PDF file is that users can scale it arbitrarily when reading on screen.

Just for the completeness: It is possible to take vector screenshots (PDF and SVG) of gtk3 applications, see the project:

https://github.com/nomeata/gtk-vector-screenshot

and the demonstrating screencast:

http://www.joachim-breitner.de/various/pdf_screenshot_3.ogv.