How to send SMS from an Ethernet shield via SMS Gateway?
First contact Clickatel's support and ask them how to use their API, make yourself familiar with it.

Then when you know that you connect your Arduino to your ethernet shield, I'm just gonna assume you got Arduino's original shield, because you want to support the arduino foundation.

http://arduino.cc/en/Main/ArduinoBoardEthernet if you have the standalone board.
http://arduino.cc/en/Main/ArduinoBoardEthernet if you have the shield board.