American Gothic in the palette of Mona Lisa: Rearrange the pixels
Java - GUI with progressive randomized transformation
I tried a LOT of things, some of them very complicated, then I finally came back to this relatively-simple code:
import java.awt.BorderLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;

import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.Timer;

@SuppressWarnings(&quot;serial&quot;)
public class CopyColors extends JFrame {
    private static final String SOURCE = &quot;spheres&quot;;
    private static final String PALETTE = &quot;mona&quot;;
    private static final int COUNT = 10000;
    private static final int DELAY = 20;
    private static final int LUM_WEIGHT = 10;
    
    private static final double[] F = {0.114, 0.587, 0.299};
    private final BufferedImage source;
    protected final BufferedImage dest;
    private final int sw;
    private final int sh;
    private final int n;
    private final Random r = new Random();
    private final JLabel l;
    
    public CopyColors(final String sourceName, final String paletteName) throws IOException {
        super(&quot;CopyColors by aditsu&quot;);
        source = ImageIO.read(new File(sourceName + &quot;.png&quot;));
        final BufferedImage palette = ImageIO.read(new File(paletteName + &quot;.png&quot;));
        sw = source.getWidth();
        sh = source.getHeight();
        final int pw = palette.getWidth();
        final int ph = palette.getHeight();
        n = sw * sh;
        if (n != pw * ph) {
            throw new RuntimeException();
        }
        dest = new BufferedImage(sw, sh, BufferedImage.TYPE_INT_RGB);
        for (int i = 0; i &lt; sh; ++i) {
            for (int j = 0; j &lt; sw; ++j) {
                final int x = i * sw + j;
                dest.setRGB(j, i, palette.getRGB(x % pw, x / pw));
            }
        }
        l = new JLabel(new ImageIcon(dest));
        add(l);
        final JButton b = new JButton(&quot;Save&quot;);
        add(b, BorderLayout.SOUTH);
        b.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(final ActionEvent e) {
                try {
                    ImageIO.write(dest, &quot;png&quot;, new File(sourceName + &quot;-&quot; + paletteName + &quot;.png&quot;));
                } catch (IOException ex) {
                    ex.printStackTrace();
                }
            }
        });
    }
    
    protected double dist(final int x, final int y) {
        double t = 0;
        double lx = 0;
        double ly = 0;
        for (int i = 0; i &lt; 3; ++i) {
            final double xi = ((x &gt;&gt; (i * 8)) &amp; 255) * F[i];
            final double yi = ((y &gt;&gt; (i * 8)) &amp; 255) * F[i];
            final double d = xi - yi;
            t += d * d;
            lx += xi;
            ly += yi;
        }
        double l = lx - ly;
        return t + l * l * LUM_WEIGHT;
    }
    
    public void improve() {
        final int x = r.nextInt(n);
        final int y = r.nextInt(n);
        final int sx = source.getRGB(x % sw, x / sw);
        final int sy = source.getRGB(y % sw, y / sw);
        final int dx = dest.getRGB(x % sw, x / sw);
        final int dy = dest.getRGB(y % sw, y / sw);
        if (dist(sx, dx) + dist(sy, dy) &gt; dist(sx, dy) + dist(sy, dx)) {
            dest.setRGB(x % sw, x / sw, dy);
            dest.setRGB(y % sw, y / sw, dx);
        }
    }
    
    public void update() {
        l.repaint();
    }
    
    public static void main(final String... args) throws IOException {
        final CopyColors x = new CopyColors(SOURCE, PALETTE);
        x.setSize(800, 600);
        x.setLocationRelativeTo(null);
        x.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        x.setVisible(true);
        new Timer(DELAY, new ActionListener() {
            @Override
            public void actionPerformed(final ActionEvent e) {
                for (int i = 0; i &lt; COUNT; ++i) {
                    x.improve();
                }
                x.update();
            }
        }).start();
    }
}

All the relevant parameters are defined as constants at the beginning of the class.
The program first copies the palette image into the source dimensions, then repeatedly chooses 2 random pixels and swaps them if that would get them closer to the source image. &quot;Closer&quot; is defined using a color distance function that calculates the difference between the r, g, b components (luma-weighted) together with the total luma difference, with a greater weight for luma.
It takes just a few seconds for the shapes to form, but a while longer for the colors to come together. You can save the current image at any time. I usually waited about 1-3 minutes before saving.
Results:
Unlike some other answers, these images were all generated using the exact same parameters (other than the file names).
American Gothic palette
 
Mona Lisa palette
 

Starry Night palette
 

The Scream palette
 


Spheres palette
I think this is the toughest test and everybody should post their results with this palette:
 

Sorry, I didn't find the river image very interesting so I haven't included it.
I also added a video at https://www.youtube.com/watch?v=_-w3cKL5teM , it shows what the program does (not exactly in real-time but similar) then it shows the gradual pixel movement using Calvin's python script. Unfortunately the video quality is significantly damaged by youtube's encoding/compression.