By no means an exhaustive list, but they key points I learned when I went through the same process:
- Price per SMS (obvious). However, some gateways give better bulk discounts. If you expect to send a lot of SMSs, this could become important.
- Carrier coverage Not all gateways support all carriers. Make sure they cover the ones you care about.
- International coverage Many gateways are region-specific. Make sure they cover all the geographies you care about.
- Integration work Older gateways have a contracts process, followed by an integration call, followed by a setup process. This can all take weeks. Newer ones like Twilio can have you up and running in a few minutes without ever needing to talk to a human.
- Support When something isn't working, what's the procedure for getting help? Is there someone you can call, or at least email?
- Performance / Uptime Honestly, they're probably all solid in this respect. But check references. A good gateway will give you a list of customers you can call to see how their experiences were.
- MMS (multi media message) support If you ever want to send multi media messages. At the time, the only company I found who could do this on all carriers was OpenMarket. May not matter to your, but if it does it greatly restricts your choices.
Ultimately, we went with Twilio and couldn't be happier. Their carrier coverage in the US is great, and the amount of effort to get up and running was trivial.
Not sure what the status of their international SMSs - if that's important to you, do some research on that in particular. They also didn't support MMS last I checked, but it sounds like that doesn't matter for your application.