Voids and hollow spheroids between ∼1 and 23 cm in diameter occur at several locations along the traverse of the Curiosity rover in Gale crater, Mars. These hollow spherical features are significantly different from anything observed in previous landed missions. The voids appear in dark-toned, rough-textured outcrops, most notably at Point Lake (sols 302-305) and Twin Cairns Island (sol 343). Point Lake displays both voids and cemented spheroids in close proximity; other locations show one or the other form. The spheroids have 1-4 mm thick walls and appear relatively dark-toned in all cases, some with a reddish hue. Only one hollow spheroid (Winnipesaukee, sol 653) was analyzed for composition, appearing mafic (Fe-rich), in contrast to the relatively felsic host rock. The interior surface of the spheroid appears to have a similar composition to the exterior with the possible exceptions of being more hydrated and slightly depleted in Fe and K. Origins of the spheroids as Martian tektites or volcanic bombs appear unlikely due to their hollow and relatively fragile nature and the absence of in-place clearly igneous rocks. A more likely explanation to both the voids and the hollow spheroids is reaction of reduced iron with oxidizing groundwater followed by some re-precipitation as cemented rind concretions at a chemical reaction front. Although some terrestrial concretion analogs are produced from a precursor siderite or pyrite, diagenetic minerals could also be direct precipitates for other terrestrial concretions. The Gale sediments differ from terrestrial sandstones in their high initial iron content, perhaps facilitating a higher occurrence of such diagenetic reactions.