I've a website that users submit their personal data to, and I'm thinking of encrypting these data using AES-256 and their password is used as a key for that encryption and then I store the encrypted data in a MySQL database...
Now if the user changes his/her password, how would I change the key of the encrypted data?
Should I gather all the data from the database, decrypt their data with the old key, and then encrypting it again with a new key?
You don't need to re-encrypt all of the user's data when they change their password.
Generate a secret key to encrypt a user's data; call this the "content encryption key." Derive a key from the user's password; call this the "key encryption key." Encrypt the "content encryption key" using the "key encryption key." Store the encrypted key along with the salt and the number of iterations used for key derivation.
If they change their password, decrypt the content encryption key with the old password, and re-encrypt it with a key derived from the new password. You should choose a new salt for the new password, and make sure you store it along with the new encrypted key.
Because the content encryption key is randomly chosen from a huge space, you can safely use ECB as the cipher mode when encrypting it.
Don't simply hash the password, even if you use salt or even if you use an as-yet-unbroken algorithm. You need to repeat the hashing operation thousands of times. There are libraries for doing this (correctly) on most platforms. Use a key derivation algorithm (PBKDF2, from PKCS #5) to create a secret key from a password.
This concept follows the draft for password-based S/MIME encryption.