Comme pour l'ensemble des Casuarinacées, les arbres du genre Gymnostoma possèdent des racines à nodules fixateurs d'azote dont la bactérie est du genre Frankia. Les rameux sont verts, grêles et articulés. Les inflorescences terminales sont portées par des rameaux courts : les mâles en chatons, les femelles capituliformes. Les fleurs sont minuscules et unisexuées. Les fleurs mâles sont verticillées à chaque nœud du chaton. Les fleurs femelles sont bi-carpellées dont un est généralement avortée, avec deux ovules par carpelle. Le fruit est un samare, protégé par les bractéoles accrescentes et lignifiées qui se séparent à maturité, donnant une apparence de capsule déhiscente.
Les espèces du genre Gymnostoma se distinguent des autres genres de la famille des Casuraninacées par des rameaux chlorophylliens quadrangulaires ou arrondis, mais non multisillonnés comme dans le genre Casurarina. Par ailleurs, les deux carpelles sont fertiles. Autre caractéristique, le genre est à x 8 chromosomes (9 pour le genre Casuarina, plus de 10 pour Allocasuarina). Enfin, ce qui donne le nom au genre, les stomates sont non protégés.
