Searching For Encrypted Fields In Data Columns

I am new to database programming and was curious how others solve the
problem of storing encrypted in data in db table columns and then
subsequently searching for these records.
The particular problem that I am facing is in dealing with (privacy)
critical information like credit-card #s and SSNs or business critical
information like sales opportunity size or revenue in the database. The
requirement is that this data be stored encrypted (and not in the
clear). Just limiting access to tables with this data isn't sufficient.
Does any database provide native facilities to store specific columns as
encrypted data ? The other option I have is to use something like RC4 to
encrypt the data before storing them in the database.

However, the subsequent problem is how do I search/sort on these columns
? Its not a big deal if I have a few hundred records; I could
potentially retrieve all the records, decrypt the specific fields and
then do in process searches/sorts. But what happens when I have (say) a
million records - I really don't want to suck in all that data and work
on it but instead use the native db search/sort capabilities.

Any suggestions and past experiences would be greatly appreciated.

much thanks,
~s