Recent advances in material science and digital fabrication provide promising opportunities for product design, mechanical and biomedical engineering, robotics, architecture, art, and science. Engineered materials and personalized fabrication are revolutionizing manufacturing culture and having a significant impact on various scientific and industrial works. As new fabrication technologies emerge, effective computational tools are needed to fully exploit the potential of digital fabrication. This thesis introduces a novel computational method for design and fabrication with auxetic materials. The term auxetic refers to solid materials with negative Poisson ratio — when the material is stretched in one direction, it also expands in all other directions. In particular, we study 2D auxetic materials in the form of a triangular linkage which exhibits auxetic behavior at the macro scale. This stretching, in turn, allows the flat material to approximate doubly-curved surfaces, making it attractive for fabrication. We physically realize auxetic materials by introducing a specific pattern of cuts into approximately inextensible material such as sheet metal, plastic, or leather. On a larger scale, we use individual rigid triangular elements and connect them with joints. First, this thesis focuses on a regular triangular linkage. When deformed into a curved shape, the linkage yields spatially-varying hexagonal openings. However, the global coupling of the linkage elements makes manual, incremental approach unlikely to succeed when trying to approximate a given curved surface. Thus, we leverage conformal geometry to enable complex surface design. In particular, we compute a global conformal map with bounded scale factor to initialize an otherwise intractable non-linear optimization. Constraint-based optimization is used to find the final linkage configuration that closely approximates a target 3D surface. Furthermore, we develop a computational method for designing novel deployable structures via programmable auxetics, i.e., spatially varying triangular linkage optimized to directly and uniquely encode the target 3D surface in the 2D pattern. The target surface is rapidly deployed from a flat initial state via inflation or gravitational loading. The thesis presents both inverse and forward design tools for interactive surface design with programmable auxetics. This allows the user to efficiently approximate a given shape and directly edit and adapt the auxetic linkage structure to explore the design alternatives. In addition, our solution enables simulation-based form-finding that uses deployment forces for interactive exploration of feasible shapes. The resulting designs can be easily manufactured via digital fabrication technologies such as laser cutting, CNC milling, or 3D printing. Auxetic materials and deployable structures enable scientific, industrial, and consumer applications across a wide variety of scales and usages. We validate our computational methods through a series of physical prototypes and application case studies, ranging from surgical implants, through art pieces, to large-scale architectural structures.