That waterbear looks very complex. How did they ever manage to find it?
So my best guess is: a mixture of mathematics, brute force searching, and lots of passionate on-line discussion with fellow nerds.
From there it's the "simple" process of designing a tape and constructor setup that will build a copy of itself at a certain offset, and delete itself upon completion.
Large parts of these macro-spaceships never get constructed or destroyed, they just travel along a support structure. That support structure is the only thing that gets constructed, and the construction recipe is encoded not in a simple "tape" glider stream but in the entire body of the spaceship.
Self-supporting spaceships like the waterbear are built with a very limited "toolkit" that only works at one particular speed. In general they're harder to put together successfully, and thus in a way are more impressive than self-constructing spaceships. Once you have a universal constructor, after all, you can build anything that's buildable. The trick is figuring out how to get along without that much power.