In this work, cellulose nanocrystals (CNCs)/polyurethane (PU) composites (CPCs) were prepared, whose microstructures and properties were studied. Interestingly, most of the CNCs dispersed in the CPCs have gathered together to form many sea-urchin-like clusters and others to form nanotows (series structures of some CNCs). A three-dimensional CNC network has been constructed by linking every two adjacent CNC clusters with CNC nanotows. The interpenetration of the PU network and CNC network has further brought about the formation of an interpenetrating-polymer-network-like (IPNL) structure in CPCs. Moreover, there are some stronger bridging actions between the two networks such as hydrogen bonds, acid-base ion pairs and induced crystallization of CNCs on the polycaprolactone (PCL) segments of PU. The mechanical properties and shape memory ones of CPCs can be significantly improved by the IPNL structure and bridging actions. More importantly, the comprehensive performance of CPCs strongly depends on the integrality level of the CNC network. The CPC3 containing 1.0 wt% CNCs has the highest integrality level of the CNC network, whose tensile strength, extensibility, modulus, and shape fixation ratio are the best among all CPCs, especially the tensile strength that shows an increase of 186% compared with the PU. Furthermore, a composite reinforcement structure composed of high-strength microfibers and “fishing net” structures is formed during the damage process, which can prevent the crack from growing. Although the crystallinity of the PU matrix decreases after the incorporation of CNCs, the grain refinement of PCL segments due to the constraint of the IPNL structure and the induced crystallization of CNCs help the performance improvement of CPCs.