It's pretty simple and you don't need to pay for a gateway.
You can send an SMS message just like an email. The wrinkle is that the email format differs between cell phone providers. When you want to do an SMS authentication, you must ask the person (on the website) for their cell number and provider name (best to use a drop-down list). Then, you must create the right email address format and send the message like a normal email. On the website, you will have a 'Continue' button and it will provide a form where they can enter the code. To get the formats for the various providers you can do a web search for something like 'PHP SMS send' and you'll probably find some sample code and as starting list of providers and formats. Any others that you need can be found by going to the web sites for the providers that you need.
Questions on working with SMS come up often enough I guess I'll have to create a tutorial but right now, this is what you get.