What's the best way to attach timber cleats to stair stringers?
You're supposed to figure that out from the load table mumbo jumbo. 

TABLE 9.14 LAG SCREW (BOLT) CAPACITY FOR SINGLE SHEAR CONNECTIONS (LBS.), page 69, Chicago deck code, PDF.

3/8ths (M10) is the middle of the road; it's better than using 1/4" or 5/16". Use stainless steel fasteners. You must pre drill your holes for cleats. Ideally it's an actually cut stringer; notice how cleats aren't even an option.