Kirigami-patterned mechanisms are an emergent class of deployable structure that are easy to fabricate and offer the potential to be integrated into deployable robots. In this letter, we propose a design methodology for robotic kirigami structures that takes into consideration the deformation, loading, and stiffness of the structure under typical use cases. We show how loading-deformation behavior of a kirigami structure can be mechanically programmed by imposing plastic deformation. We develop a model for plasticity in the stretching of a kirigami structure. We show the creation of kirigami structures that have an increased elastic region, and specified stiffness, in their deployed states. We demonstrate the benefits of such a plastically-deformed structure by integrating it into a soft deployable crawling robot: the kirigami structure matches the stiffness of the soft actuator such that the deployed, coupled behavior serves to mechanically program the gait step size.