Best Way to Encrypt Customer Information in My Com

So long story short, our company recently had an intrusion wherein our MySQL DB was dumped and stolen. The execs are really nervous now and in addition to upping other security measures, they are intent on encrypting all customer information (email address, home address, names, and the like) in the DB.

I am unsure of where to begin on this. We run a PHP app. Obviously, this is going to create some additional overhead that we'd like to minimize. Another concern is going to be the difficulty in changing the code wherever the new encrypted fields are used.

This strikes me as an unnecessary precaution, but management seems firm on it.

What type of encryption algorithm/method would be best for this use case?

There is a very good writeup on how to do this with MySQL here: http://thinkdiff.net/mysql/encrypt-mysql-data-using-aes-techniques/.

You'll want to use AES with 256bit keys, as that is the prevailing best-practice/standard right now. 256bit AES keys are considered to be of sufficient size to be secure against modern computing power.

It's a good idea, regardless of if you think it's overkill or not, to encrypt your database. Even if the data isn't horribly sensitive, the loss of customer records can be very embarrassing to your company, at the very least, and could adversely affect customer confidence and people's willingness to hand over their data in the future. Encrypting the full contents of your database may not be industry-standard right now but trends are moving that way and it cannot hurt you to adopt a stronger security posture. If nothing else, think of it as another entry in your Defense-In-Depth implementation.

I would also recommend you check this article out - http://www.symantec.com/connect/articles/secure-mysql-database-design - as it provides a good, fairly basic, introduction to secure database system design that should give you some pointers on other things to check for your application.