The big question in my mind is always "Does the server need to be able to decrypt that data?" If the server has the decryption keys, the attacker can probably steal them along with the encrypted data. I store GPG encrypted data on servers where they only have the public key - retrieving the data involves grabbing the encrypted data from the server and decrypting it somewhere else that has the private key available. (This is a handy trick for web forms that collect sensitive data - serialise it and GPG encrypt it immediately, then you can happily send the encrypted blob via non-100%-reliable email,and have the local encrypted blob available if the email copy fails to arrive.)
But please define sensitive data more in detail. Are we talking about passwords, messages or photos of passports etc?
Encryption. I'm thinking public key might work, but if I want to decrypt on the server how do I keep private keys private?
If you only need protection against skript kiddies running automated attacks - look at how Apache/OpenSSL deal with passphrase protected private keys. They go to some length to ensure the decrypted private key only ever exists in-memory, and doesn't get written to disk, but someone who's escalated to local root can (I'm pretty sure) grab the key out of ram (core dumping the whole process, if need be).
If you _have_ to have sensitive data stored and available to the server - consider storing the sensitive/encrypted data on a separate system with a much smaller attack surface than a publicly available web server (assuming that's what we're talking about here), with a extremely tightly specified API that's small and well defined enough to make it practical to come much closer to fully auditing the code - and where it's practical to monitor the API for intrusion or unexpected requests and shut it down pre-emptively before you lose your whole database.
Mostly though, I advise working out a way to not have to do that.
(Note that "storing credit card details" immediately confers the whole responsibility of PCI compliance on you. It is, in my experience, almost _never_ worthwhile doing that - leave that headache to Stripe/Square/Paypal/whoever, and re think your business process to suit.)
Secure from remote but unskilled attackers using auto tools poorly?
Secure from remote but skilled users targetting your system?
Local and skilled users targetting your system?
Law enforcement smashing the door down?
Well formed legal documents?
Well funded government agencies?
Malicious employees?
It does help if a thief walks out with your server, or if some extremely uneducated and unprofessional law enforcement power down your server as they serve their warrant on your datacenter - but neither of those scenarios are anywhere near the top of the "reasons your sensitive data got compromised and showed up on pastebin" lists.