For a great free library, I highly recommend BouncyCastle. It is actively maintained, high quality, and has a nice array of code examples. For reference documentation, you'll have to rely more on the general JCE docs.
I can't say what library we use to meet FIPS certification requirements. But there are alternatives to CryptoJ that are much, much cheaper.
In general, I'd recommend generating a new key for each message you encrypt with a symmetric cipher like Rijndael, and then encrypting that key with an asymmetric algorithm like RSA. These private keys can be stored in a password-protected, software-based key store like PKCS #12 or Java's "JKS", or, for better security, on "smart card" hardware token or other crypto hardware module.