How should I build up stair stringers (instead of cutting them out)?

Fastening the wood triangles to the 2x6 can be done in a number of ways such as glue and dowel rods as suggested in another answer. The addition of a plywood scab on the side as suggested in a comment is even better.

But also consider that as drawn in your picture the construction of a stairway with triangles cut at 45 degrees would produce a stairway with narrow steep steps such as you might find in some house built 120 years ago. Modern stairways are built with the rise of each step less than the run of each step. If you were cutting your triangles out of reclaimed 2x6's (which are 5.5 inches wide) you would want to cut them more like the right hand side of the below picture.

The angles and dimensions as shown to the right above are only an example and may very well not be exactly correct for your application or even within the range of code standards for stairs. Keep in mind that the design of a stairway requires careful calculations, taking tread thickness and flooring thickness at the head and base of the stairs into account so that all the steps are a uniform size. Uniformity is important for building code compliance and safe usage of the stairway.