Don't store a key at all and derive it from the user password. This is the only really safe way, because not even the server can decrypt the data then. The cons are of course, that the user needs to enter the password every time he uses your service. If the user changes the password, you need to re-encrypt all data. If the user forgets the password, the data is lost.
Place the key in a place as secure as you can. That means, it should surely be placed outside of the www-root directory in an inaccessible directory on the server. Depending on the importance of the data, you can also consider to outsource encryption to another dedicated server.
@neanderslob - There is a library Zend/Crypt which is often recommended, though i never used it myself, because it probably requires the Zend framework. To do it yourself, choose a mode that uses an IV (like CBC, but not ECB). The IV can be combined with the resulting cyphertext. Then use a binary string of the required length as key (often 32 bytes), not a short password. A simple example you can find on my homepage search for encryptTwofish().
Encryption cannot solve the problem of securing data, it can only "concentrate" it to a key. Wherever you store the key, your application must be able to decrypt the data, so can do an attacker. There are two possible solutions to this problem i know of:
Now THAT makes sense! Thanks for your answer; it seemed like everything I read online was dancing around this fundamental point (probably because it's understood by most and therefore isn't worth reiterating). Also good to know on your AES_ENCRYPT point. Is there a tutorial out there that you would recommend to get me started on a good encryption practice for PHP? Clearly I'm planning on Googling one up for myself but I was just wondering if there was anything that you might recommend. Thanks again for the help.
P.S. I would recommend to encrypt the data before storing it to the database, because MySQL AES_ENCRYPT uses the ECB mode without an IV. This allows to search for a certain value, but is less secure (i'm pretty sure that you don't want to search by password).
You stumbled over the biggest problem with encrypting data in the database: