I'd just like to add a few things to John's excellent post.

An amplification: Changing keys regularly is always good cryptographic practice. It reduces the amount of data you lose from a single compromised key. It's only with some ciphers (like RC4) that changing the key becomes critical.

In your mail application, you'll definitely want it to be possible to change keys without a major hassle. Maybe you'll want to use per-message session keys, each encrypted with a (changeable!) master key. Maybe using the same key for everything, and changing it once a month, is enough. Sorry we're all giving the same non-answer, but it depends on your requirements.

Yes, random IV's are good. By default, Crypt::CBC uses them.

A minor correction: AES uses 128-bit blocks, not 256-bit. Rijndael goes up to 256-bit blocks, but the AES specification doesn't include that. I can't think of any other cipher that uses such large blocks, and there's really not much reason for them. A birthday attack against a 64-bit block cipher (like DES or Blowfish) in a chaining mode is going to need around 30 gigabytes of encrypted data before you expect to see the same block twice. With 128-bit blocks, that goes up to 2**68 bytes, or sixty thousand years at gigabit ethernet speed.