I'm running KDE4.2, and Klipper does not paste image data, so dbus is
not an option. I settled on using Qt: you will need the command
"getclipboardimage" installed on your $PATH (Qt 4.4 source code and
instructions available at http://www.phys.ucalgary.ca/~burchill).
Perhaps someone could suggest how to do this from perl or python,
etc...

Adding the "Paste Image" to the edit menu involves editing a user-copy
of $InstallationDirectory/SystemFiles/FrontEnd/TextResources/X/
MenuSetup.tr. Caution: a typo in this file can break mathematica.

Add the following between the &Paste and Clea&r\tDelete menu items:

MenuItem["Paste &Image",
KernelExecute[{Module[{tmpFile, image, file},
tmpFile = ToFileName
[$TemporaryDirectory, "clipboardimagefileformathematica.png"];
DeleteFile[FileNames[tmpFile]];
file = Import["!getclipboardimage "
<> tmpFile, "Lines"];
If[Length[file] > 0, image = Import
[file[[1]], "Image"];
If[Head[image] === Image,
NotebookWrite[InputNotebook[],
Cell[BoxData
[ToBoxes@image],"Output"]]]];]}],
MenuKey["V", Modifiers->{"Control"}], MenuEvaluator-

>Automatic],

Restart mathematica. Try it out by opening a PDF file, selecting an
image and copying it to the clipboard. In a notebook select "Paste
Image" from the Edit menu. This inserts the image in-line.