I'm wondering whether deleted SMS on Android phones are retrievable? If so, how is this done? How can one avoid it?
Everything is retrievable if it's not overwritten. On solid-state devices like our phones we need to be careful to start from an encrypted starting point to avoid some of the theoretical recovery (ForensicsWiki).
Short answer, Oxygen is something I've used to pull data off phones, but all it really requires is physical access, take a physical image, and use forensics tools like FTK or EnCase to look through hex a little easier. Better yet, use Oxygen to make the everything pretty and organized (http://www.oxygen-forensic.com).
Short short answer, you need to overwrite your data / encrypt the data to avoid recoverability. Even then I'm sure some wizards could get bits and pieces given enough time.