But what if someone changes their password? Then their password key
won't be able to access their encrypted messages. What's the best way
to go about this?
When someone changes their password, every system I am familiar with requires the user to type in both the old password and the new password.
If there is only a small amount of encrypted data, and you want your user to be able to access that data with only the new password, the simplest approach is to decrypt all that data with the old password to recover the plaintext, and then encrypt the plaintext using the new password.
My understanding is that many systems have several levels of indirection.
When someone wants to read the plaintext of one document, behind the scenes what really happens is the typed-in password is used to decrypt a keyring that stores (in encrypted form) a master key.
(typically the "~/.ssh/id_rsa" file or the "~/Library/Keychains/" file).
The encrypted document is typically stored in RFC 4880 OpenPGP Message Format or something similar.
The master key is used to decrypt one of the blocks in the header corresponding to that master key, giving the unique symmetric key used only for the body of this one document.
Then that symmetric key is used to decrypt the body of the encrypted document, producing the plaintext.
When someone changes to a new password, generally the old password is used decrypt the entire keyring, and then the system encrypts the keyring with the new password.
All the files are still accessible to that user, because the exact same master key is used to decrypt that file.
Alternatively, for each document the user has permission to access, one could add another block to the header of that encrypted file that contains an encrypted version of the same document-unique symmetric key, encrypted by a fresh new master key.
Ideally the user would carry around his own keyring and no one else would ever have access to it.
In practice, many systems store an (encrypted) keyring for each user.