How do native sulfur crystals form?
Tl;DR: Wikipedia mentions some of the ways in which elemental sulfur is produced naturally:

Through volcanic emissions, including emissions from hydrothermal vents. Some of them found near hot springs and near volcanic deposits. Also, lakes of molten sulfur up to ~200 m in diameter have been found on the sea floor due to submarine volcanoes.
As minerals: sulfide minerals, such as pyrite (iron sulfide), cinnabar (mercury sulfide), galena (lead sulfide), sphalerite (zinc sulfide), and stibnite (antimony sulfide); and the sulfate minerals, such as gypsum (calcium sulfate), alunite (potassium aluminum sulfate), and barite (barium sulfate).
Action of anaerobic bacteria on sulfate/sulfide minerals.


Long answer:
I found a paper1 which discussed #3 point in details. It said that although sulfide minerals can be oxidized to zero-valent sulfur by sulfate reducing bacteria in presence of molecular oxygen, it may pose the following problems:

exposure to oxygen would drastically decrease growth of microbes thereby slowing down sulfide production
on geologic timescales, excess supply with oxygen would convert
sulfide into sulfate rather than native sulfur
enormous amounts of oxygenated water would be needed to produce sulfur in large amounts

So, in order to overcome these problems, scientists proposed four possible mechanisms as a means to form native sulfur:

a modified sulfate reduction process that produces sulfur compounds
with an intermediate oxidation state,
coupling of sulfide oxidation to methanogenesis that utilizes
methylated compounds, acetate or carbon dioxide
ammonium oxidation coupled to sulfate reduction
sulfur comproportionation of sulfate and sulfide.

These reactions are found to be thermodynamically favorable and especially useful in environments containing dissolved sulfide. This provide evidence that microbial species functioning in such environments can produce native sulfur in absence of light and external oxidants such as $\ce{O2}$, nitrate, and metal oxides.
Reference

Labrado, A. L., Brunner, B., Bernasconi, S. M., &amp; Peckmann, J. (2019). Formation of Large Native Sulfur Deposits Does Not Require Molecular Oxygen. Frontiers in microbiology, 10, 24. https://doi.org/10.3389/fmicb.2019.00024