Tk.pm uses "findINC" subroutine which helps with finding an image near module installation, look into it to see the logic.

Other approach (used in many Tk modules) is to base64-encoding image data into PM file itself.

But in general, this is indeed a bit of a problem, without sole solution, and each module uses its own way.