They never seem to mention that in the paper, at least not prominently as I of course skimmed it today. But Photoshop already has a built in tool for this, so I guess they can just use the standard methods that seem to work fairly well.
PaintMatch algorithm: http://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/index.php