Firstly, this is an excellent question.
Marius created the reforms during his time as proconsul after Rome's struggles in the first half of the Cimbrian wars against the Northern Rhone-located Cimbri and Teutons tribes. The absolute destruction at Arausio was part of the reason for the reform's institution. It is unlikely that any battle led before Arausio including Arausio used the reforms- many sources including the Wikipedian articles upon the Cimbrian war state the Roman forces in terms of strict numbers and tend to only use the term "legions" and "cohorts" after and in the battle of Aquae Sextiae.
For this reason, I think we can deduce the first use of the legions was at Aquae Sextiae.
Marius eliminated the manipular system and invented the term "cohort".
Another reason I think we can state with solidarity that Aquae Sextiae was the first usage is because of Marius's reform that allowed non aristocratic plebeians to join the army. This would only have been done due to the absolute deficit of Roman soldiers, which would have occurred after the loss of 80,000 at Arausio.
The system eliminated many of the conventions of the Republican army and ensured that a fully staffed and annually paid Roman army was always at hand. I found this to be an excellent source detailing many of the impacts of the war and the changes in the Army post triplex acies.
I hope this helped and gave a better idea on the reforms and approximate time of the institution of the reforms.