Delete messages, photos/videos, and call records to deter an unsophisticated attacker, but remember that deleted data can sometimes be recovered from the phone.
Don’t use the phone book if you can keep numbers in a safe place without it. Don’t store numbers and names together.
Do not use explicitly identifying information for contacts, including names, nicknames, or contact icons/pictures.
Check the settings on the phone to see if it can be set to NOT store call logs and outgoing SMS.
If you have a smartphone, enable remote wipe or ‘poison pill’ functionality. This allows you to remotely erase data on the phone if it has been stolen. You will need to download an app and/or configure remote wipe through an online service. There are more details in this article: http://www.pcmag.com/article2/0,2817,2352755,00.asp
Lock your phone using various available options to block calls and physical access.
Always use removable memory/external storage for sensitive media and data, and remove it whenever the phone is not with you.