What is the best way to marry an unlawful non US citizen?

Getting married should not be an issue as long as he has some type of valid ID like passport. Then you can file for his green card on the basis of marriage to a US citizen, provided he entered the US lawfully and can prove that lawful entry.

Issues of marriage and family are matters delegated to the several states and each state including Arizona may set the standards and procedures for obtaining marriage licenses. I practice in New York, a state that has no such restrictions. I am unaware of Arizona marriage license rules, but if that state indeed requires proof of immigration status as a condition for obtaining marriage license in Arizona, I am afraid its decision will be valid as a matter of law. However, even if you live in Arizona and will file your green card in that state,.you do not have to get married in Arizona. and I am certain other states like New York do not have such restrictions. You should consider marrying your fiance in another state.

If you are not comfortable to marry in Arizona, you should go to Vegas or California. She can show her passport as ID you can get married.

Even if his authorized stay in the US as a visitor has already expired, he can still apply for adjustment of status after he marries a US citizen. If you are concerned that Arizona may report him to ICE, have you thought about getting married in another state, such as Nevada or New Mexico?

You should both talk with an Immigration Attorney about the details of your case. The Attorney can advise about your chance of success and any potential problems you could face in the process.

You can marry and apply for the green card. He should be fine as long as he entered with a visa (even if he overstayed). The entire process should take between 3 and 6 months from start to finish.