It sounds simple enough, but actually putting it all together is the difficult part. Kerimil shows you had to create an App for Android using App Inventor, gives you a default sketch and takes you into blinkydom.
The app is simple, turn an LED on, turn an LED off. Kerimil steps it up a notch by using voice commands on the phone. This is a great start for getting more complex apps to work. Writeup / source here.
He later added some videos where he apparently improved his sketches sending data from the Arduino to a web site via the phone. Writeup / source here.
Then moving right along to alerting the Arduino to an incoming SMS message.
Really awesome stuff, with just the ingredients shown here you could craft some really cool things to automate your home, control a robot, or whatever.