How would I go about building a craigslist-type phone verification system, which, when given a phone number, either texts or calls the number with a code that the user can use to verify that it's their phone?
... says they are only evaluating SMS at this time but an SMS gateway would be much easier to find out there (someone in the thread even pitches an option, http://www.textmarks.com )
Using an SMS aggregator such as CellTrust, you could send the user a code through a shared short code. Or, if you're willing to put up with short ads at the bottom of messages, you could try TextMarks.
Looks like textmarks requires the person to subscribe before you can send messages to them: "To keep everybody happy and prevent abuse, you can only send texts to subscribers of your TextMark."