Actually KMS doesn't have to be a cloud service or expensive enterprise solution (although, it's the most secure way). It can be just another server outside of the "war zone" (separate network) which stores and "tells" the key only to the trusted server.
Even more, the keys usually are stored encrypted themselves. The key which you encrypted the key with is called key encryption key, or KEK. Just FYI, it's a very vast field for googling, reading and learning.
Finally, you can store it somewhere else, in depths of your network and this is the most complex but secure thing, called KMS - Key Management Server.
I could write a book ~300 pages about managing keys, as I have supervised many quite sensitive data projects complying with PCI DDS3 security standards. You can google for key management and try to find some easy tutorials and schemes.
Thanks for replying. I'm glad to hear from someone with experience in this, it's been helpful; didn't know about KMS before. At least I was thinking along the right lines with storing the encryption key on the server, I'll probably go a head with that implementation. Thanks again, Neil.
Yes, the key (password for decrypting data) has to be stored on the server.
There's no way around this, unfortunately.
You can make your scripts get the key (or second database credentials) from some other script/app on the server, thus improving anti-transparency. In case someone will gain access to first script, he may not gain access to the other.
You can store it in a different, separate database, with separate set of keys.
You can store it in form of a plain text file, somewhere in a folder outside of the users access zone, where only root system user will be able to get it.