You have to know how to read these papers, and set your expectations low. The prior ability to do anything of this sort was so low that any advance, even a highly imperfect one, is exciting and unexpected.
It's like one of those animal trick shows, where the cute dog sits in front of the piano and plays Happy Birthday on it. You're not expecting Beethoven's Moonlight Sonata or mastery-level playing. It would be churlish to complain that the piece was overly simplistic, the playing lacked expression, and halfway through, the dog got distracted and started chasing his tail and never finished playing. Come on, it's a piano-playing puppy! How often do you see that?
Same deal here. It's probably not really fully capturing "style" as a human would consider it.
Don't think of this as transforming an image to make it look like it was painted by some specific painter or artist. It's not going to take my cellphone-snap of a tree in my backyard and make it look like an Ansel Adams composition. Don't think of this as learning the style and idiosyncracies of a particular painter. Don't even think of this as learning "style" as humans would consider it.
Rather, what they do is propose a technical transformation to an image, and then they look at its effect on some examples and -- woah -- the effect is pretty cool! In some cases it comes surprisingly close to mimicking some aspects of human style. It's not wonderful, but hey, it's more than one would otherwise expect.
At a technical level, they identify some particular attribute or property of an image that they can compute: if $I$ is an image, let $f(I)$ denote the value of this attribute. Then, given an image $I_1$ and an image $I_2$, they show how to modify $I_2$ to get a new image $I'_2$ such that $f(I'_2)$ is similar to $f(I_1)$. They look at some examples and empirically find that (a) $I'_2$ often seems to have "similar visual content" to $I_2$, and (b) $I'_2$ often seems to have captured some of the aspects of "artistic style" of $I_1$ (it seems to have a similar "style" as $I_1$), in some vague sense.
Based on this, they decide to call $f(I)$ the "style" of $I$. That's probably playing a bit fast and loose with naming, as I suspect $f(I)$ falls far short of always capturing all of the elements of artistic style as a human would judge it.
At a technical level, $f(I)$ is computed by computing some kind of correlation matrix on the responses of internal layers of a particular neural network when applied to image $I$... or something like that. The details don't matter so much, as the fact that empirically their transformation provides results that are interesting and unexpected.
And that's why they don't require a large training set per artist: they don't try to capture anything specific to a single artist. They're not doing what you seemed to expect them to be doing. Also, the neural network was obtained by pre-training it on a dataset of millions of images, so it probably captures some kind of information about typical patterns that are seen in images.