Появилась мысль, сделать уведомление об изменениях на сайте через смс (сайт на php, оператор: мегафон). Если кто сталкивался с этим подскажите как грамотно все реализовать?

Проще паренной репы.
У всех операторов есть услуга mail2sms - это когда номеру присваивается e-mail адрес, и письма отправленные на этот адрес приходят в виде СМС.
http://sibir.megafon.ru/services/misc/email2sms/

Реализовать отправку письма на E-mail из php - это вообще не вопрос. Стандартная функция mail()

Огромное спасибо, а то устал гуглить, столько всякой ахинеи пишут на эту тему =)

а другие способы есть?

а если бы и были, то зачем ? это самое простое решение, а следовательно самое лучшее.