Here is what I believe they did, judging from your linked news article and their article on arxiv:

They start with a single green photon (photon with a wavelength of 532 nm), and send it through a beam splitter. This object does exactly what is sounds like it should do: you take a light beam and it splits it into two light beams of half the intensity. And if you send in a single photon it goes into a superposition of taking both paths (similar to the double slit experiment, except that the two paths are immediately recombined there and here they are not). Then in each of the paths they place a downconverter, which will transform a green photon into a yellow photon and a red photon (actually both are infra-red, but the naming scheme is easier for explaining what happens). So now our original photon is in a superposition of being a yellow plus a red photon in path 1 and being a yellow and a red photon in path 2.

An important thing about downconversion is that is has to preserve all kinds of invariants, in particular momentum and energy. Therefore if you know everything about the photon that goes into a downconversion process (here: a green photon. And 'everything' is very inaccurate - here they care only about the momentum, i.e. in which direction it is going, and its energy, i.e. which colour it is) and you measure just one of the two photons that come out of the downconversion (the red one or the yellow one, you can pick) you perfectly know what happened to the other photon. They make clever use of this later.

So: photon in a superposition of being yellow and red in path 1 and being yellow and red in path 2. Now they place a colour-dependent mirror in path 1, sending the red photon and the yellow photon from path 1 in different directions. They place their micro-scale picture of a cat in the path of the red photon from path 1. So intuitively we now have three paths: a Path 1 - red photon, which has a picture of a cat in its way, a Path 1 - yellow photon which has no obstacles and a Path 2 with no obstacles. Our original photon is still in a superposition of being in both sections of Path 1 and being in Path 2.

Now they recombine all three paths, in such a way that they make sure that Path 1 and Path 2 interfere destructively at the surface of the camera, which registers yellow photons (and only yellow photons). So no clicks at all, you'd say. But this is only the case if our red photon in Path 1 doesn't hit the cat-shaped object, in which case the blob of the wavefunction that went through path 1 is identical to the blob that went through path 2, so they can interfere. If the red photon did hit the micro-cat then the blob of amplitude that went through Path 1 no longer describes a red and a yellow photon, but only a yellow photon and a faintly vibrating image of a cat! [1] This blob can no longer interfere destructively with the blob that went through Path 2 (since they are now completely different when viewed in configuration space), so in particular the amplitudes for the yellow photon no longer cancel out. So now the camera gives a click.

And the best part is that from this down-conversion the direction of the red photon that was speeding towards that cat and the direction of that yellow photon in Path 1 are perfectly (anti-)correlated (the two photons are entangled), so when the red photon hits the cat just a little bit lower (which is just the same as saying that a little bit lower there is still some cat left, provided you try the experiment sufficiently many times) the yellow photon in Path 1 is going upwards a bit more (as the red one went downward) and your camera registers a click just a little bit higher on its surface of photoreceptors (or, more accurately - if red photons in Path 1 that go down hit the picture of the cat, then yellow photons that go up don't interfere with Path 2, so after recombination there is some uncanceled amplitude of a Path 2 yellow photon going upwards, which registers on your camera as a click high on the vertical axis). Same for the horizontal direction. So with this experiment you'd get a picture of your cat rotated by 180 degrees, as you only register a click when the amplitudes of the two paths no longer interfere, i.e. something has happened to your red photon in Path 1.

The arxiv paper has two enlightening overviews of their actual setup on pages 4 and 6, especially the one on page 4 is insightful. The one on page 6 just includes more equipment needed to make the idea actually work (for example these down-converters are not perfect, so all your paths are filled to the brim with green light, which you need to filter out, etc. etc.).

-

1) There is a very important but subtle step here - since the yellow and red photon from path 1 are created through down-conversion, they are perfectly entangled, and therefore as soon as we ensure that certain states of one of these two photons undergo interactions while others do not the resulting wavefunction can never be written as a product of a state for the red photon and the yellow photon. This is needed to ensure that at the recombining not only does the overall amplitude of Path 1 not interfere with the overall amplitude of Path 2, but that furthermore the wavefunction of the red photon in Path 1 cannot interfere with the wavefunction of the red photon in Path 2. [2]

2) The footnote above is a rather horrible explanation - a better explanation involves doing the mathematics. But the important bit to take home is that if you use anything less than a downconversion process to double up your photons even though you mucked up the red photons from Path 1 the yellow amplitudes from Path 1 and 2 might still happily interfere, which you do not want. It is vital that by poking at the red photon in Path 1 the total blob of path 1 completely ignores the total blob of path 2, even without touching the yellow photon in Path 1.

As with most things about quantum mechanics, it's just lousy reporting. The paper is novel and interesting, but not for the reasons described by that article.

This is the (conceptual) setup used by the experiment: http://www.nature.com/nature/journal/v512/n7515/images/nature13586-f1.jpg

NL: nonlinear crystal (mixes or separates light frequencies), BS: beam splitter, O: object, D: dichroic mirror (mirror that reflects or refracts differently depending on wavelength).

The main thing that makes this special is that from the 'photon' point of view, no photon that touches O ever makes it to the detectors. Instead, information is carried to the detectors via entanglement.

From the 'wave' point of view, there's nothing strange about the setup, it's just ordinary classical wave interference in NL2 (with some nonlinear effects thrown in). The thing is, though, that just like the double-slit experiment, the interference persists even when there is only a single photon entering the setup.

This has absolutely nothing to do with many worlds. Also, the article title is sensationalist, what a surprise.

This is yet another counter-intuitive but well understood manifestation of entanglement: one side interacts with something (in this case the cat stencil), the other side interacts with something else (in this case the screen), and the outcomes are correlated. The second splitting is a really neat trick, Anton Zeilinger is famous for performing ground-braking experiments in quantum mechanics. His work is always exquisite and can certainly be trusted. Some day this may have interesting applications, too:

One advantage of the technique is that the two photons need not be of the same energy, Zeilinger says, meaning that the light that touches the object can be of a different colour than the light that is detected. For example, a quantum imager could probe delicate biological samples by sending low-energy photons through them while building up the image using visible-range photons and a conventional camera.

But, again, one does not need to invoke many worlds to understand/explain what is going on here.

I think this is just a more-involved version of the Elitzur-Vaidman bomb tester. The main difference seems to be that they're going out of their way to make sure the photons that interact with the object are at a different frequency.

The quantum bomb tester works by relying on the fact that the two arms interfere with each other to prevent one of the detectors from going off. But if there's a measure-like interaction on one arm, that cancelled-out detector starts clicking. The "magic" is that it can click even when the interaction doesn't occur. (I think the many worlds view here is that the bomb blew up in one world, creating differences that prevented it from ending up in the same state as. and thus interfering with. the non-bomb-blowing-up worlds.)