1)
Seeing as one may not use iron on the Mizbe'ach and bearing in mind that they did not have the Shamir worm (that can bore into stone) until the time of Shlomoh ha'Melech, how could they write on the stones?
1.
Moshav Zekenim #1: They covered them with lime, and wrote on the lime.
2.
Moshav Zekenim #2: In fact, they had the Shamir from the time of Moshe and Shlomoh learned from Moshe, as the Gemara explains in Gitin 68a.
