Andrew,
"Cutting" the notches is done with SketchUp's "intersect" feature. Here you can see my results, for the first puzzle:
Note that the left puzzle (red/yellow) has lines that define notches, while in the second puzzle (green/cyan,) the sticks cross each other, but no notch lines are present, since the "intersect" step has yet to be done.
Here is where I processed the intersections to produce the notches. Each notch-depth is "halved," so that the intersection overlap is equally shared by the two involved sticks.
Note that the stick lengths differ, and the notch depths and angles differ, as well:
Since I made the puzzle sticks as SketchUp components, notching one modifies all similarly-named component sticks. So, if a modify one of the yellow sticks, the other 59 yellow sticks in the puzzle change, as well. The same concept applies to editing the 30 red stick components - by editing just one of them.
Final desired results:
-Taff