What does "elementary" mean in this context?
[0] http://conwaylife.com/wiki/Knightship
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.
There are "optional extras" that can be added or removed from some spaceships. These are called "tagalongs", and aren't considered to be part of the ship. That can get a little complicated, too, though, like with another recent-ish discovery: http://conwaylife.com/wiki/Fireship .