It bears mentioning that any solution that is per machine or per user is not terribly useful for applications that store data in a database that is potentially to be read by multiple users on multiple machines during application runtime. Most use cases cannot make an assumption that data a given user posts is only expected to be read by him.
This is my best practice for storing and generating/using encryption keys in applications. Your mileage may vary if you have usage requirements that can't accommodate this scheme.
First, along with my application, I distribute an application-specific configurator to my customer. This configurator is run by my customer's administrator who installs the application and the database, which resides on a Microsoft SQL Server.
After running the installer, the admin runs my configurator. The configurator allows him to specify sensitive information, such as their SMTP server credentials needed for the application to send email, etc.
The configurator uses a private master key, which is hardcoded in a DLL. This embedded key is different per distribution. The sensitive information is encrypted and then stored in the registry by the configurator. The master key is also used to encrypt/decrypt other encryption keys that are generated at runtime to encrypt/decrypt application data.
At application runtime, another key is generated for general application data encryption - stuff like passwords and other sensitive info to be stored in the database in encrypted form. This key is encrypted using the master key from the DLL previously mentioned, and it is then stored in the registry as well.
Every time the application needs to encrypt or decrypt data to and from the database, it uses the master key to decrypt the application key. The application key is combined with a different IV each time. Each new IV is simply prepended to the data, as some of the other answers here have described.
When decrypting, the application simply clips the IV off the front of the data payload, and uses it along with the application key from the registry to decrypt the remainder of the payload.
By using this scheme, the only risk is that it could be read from memory. Secure strings can be used to minimize that risk if you're that concerned about it. Most of my clients don't expect their users to be hooking up to JTAG ports of motherboards and trying to read and decipher memory contents, but hey... your mileage may vary.