We present results of Brownian dynamics simulations of tethered nanospheres and tethered nanorods. Immiscibility between tether and nanoparticle facilitates microphase separation into the bicontinuous, double gyroid structure (first reported by Iacovella et al. [Phys. Rev. E 75, 040801(R) (2007)] and Horsch et al. [J. Chem. Phys. 125, 184903 (2006)], respectively). We demonstrate the ability of these nanoparticles to adopt distinct, minimal energy local packings, in which nanospheres form icosahedral-like clusters and nanorods form splayed hexagonal bundles. These local structures reduce packing frustration within the nodes of the double gyroid. We argue that the ability to locally order into stable structures is key to the formation of the double gyroid phase in these systems.