Hexagonal honeycomb structures are known for their high strength and low weight. We construct a new class of fractal-appearing cellular metamaterials by replacing each three-edge vertex of a base hexagonal network with a smaller hexagon and iterating this process. The mechanical properties of the structure after different orders of the iteration are optimized. We find that the optimal structure (with highest in-plane stiffness for a given weight ratio) is self-similar but requires higher order hierarchy as the density vanishes. These results offer insights into how incorporating hierarchy in the material structure can create low-density metamaterials with desired properties and function.