Porous polymer networks (PPNs) are a class of advanced porous materials that combine the advantages of cheap and stable polymers with the high surface areas and tunable chemistry of metal–organic frameworks. They are of particular interest for gas separation or storage applications, for instance, as methane adsorbents for a vehicular natural gas tank or other portable applications. PPNs are self-assembled from distinct building units; here, we utilize commercially available chemical fragments and two experimentally known synthetic routes to design in silico a large database of synthetically realistic PPN materials. All structures from our database of 18,000 materials have been relaxed with semiempirical electronic structure methods and characterized with Grand-canonical Monte Carlo simulations for methane uptake and deliverable (working) capacity. A number of novel structure–property relationships that govern methane storage performance were identified. The relationships are translated into experimental guidelines to realize the ideal PPN structure. We found that cooperative methane–methane attractions were present in all of the best-performing materials, highlighting the importance of guest interaction in the design of optimal materials for methane storage.