This is the most detailed construction information I have been able to find. It is presented for directions for making a puzzle in The Art Of Whittling: Classic Woodworking Projects For Beginners And Hobbyists by Walter L. Faurot [Archive.org].

I have transcribed the written instructions below:

Puzzle No. 1
One of the simplest of the many articles possible to make, is the puzzle in Figure 1, Plate 2.

Procure a stick 12 to 14 inches long, Figure 2, and dress it down until it is about 3/8 or 1/2 inch square.

Cut into six equal lengths and on five of these pieces cut notches, as shown in Figure 3, a, b, c, d, and e. The sixth piece f, remains as square and smooth as it was originally in Figure 2.

Now, if the notches have been properly cut, the puzzle will go together perfectly and form a tight, solid cube as in Figure 1.

Putting the puzzle together is done as follows: Hold piece a, Figure 3, in the left hand with the notches uppermost. Place piece b against a as shown in Figure 4. Next place piece c on the other side of a and parallel with b. The three then appear as in Figure 5.

Next, lay the pieces d and e across piece a and against pieces b and c; being sure that the third notch is upright on both, as in Figure 6.

Piece f, the key, can now be pushed through the hole formed by the notches in the other five pieces, making the puzzle complete, as shown in Figure 1.

Here is another set of instructions describing a technique for “the Indian six-stick or cane-end puzzle” from Whittling and Woodcarving by E.J. Tangerman [Archive.org]. Again, I have transcribed the instructions here:

Another old-timer is the Indian six-stick or cane-end puzzle, made from 1/2-in. wood — maple, mahogany, white pine, basswood, or any other. I learned it from an Indian who used it to decorate the head of a cane or walking stick, but it may also be made with six equal-length pieces as a hand puzzle. Whittle a piece of the wood you select 10 in. long and 1/2 in. square, then cut it in five 2-in. pieces. Be sure the sides are square and smooth. Notch all five, as in Fig. 69 a1, cutting one notch each side of the center from one edge down to the two adjacent ones. Each notch should be right-angled so that one of the other pieces will fit it closely, the bottom of each notch should go squarely across the piece, and the inner ends of the notches should just meet at the top.

Now notch two of the pieces with a third notch, as at Fig. 69 a4 and 5, from one adjacent edge and exactly between the other two. Take the top of your walking stick or cane and whittle a section 2 in. long exactly square, as in a6.

Put 1 and 2 together to form a cross as at b, 2 fitting into the lower notch of 1 with its two notches turned up. Now fit 3 against 1 and around 2, as in c so that the upper notches in 1 and 3 form a square hole. Lay pieces 4 and 5 on each side of 1 and 3 with center notch up. The two notches in 4 and 5 will fit closely against 1 and 3, and they will in turn fit into the notches in 2. Now simply push 6 into the square hold that is left, as in d, parallel to 2, and the cane end is finished. If you wish, use different colors of wood.