I am a programmer/analyst in a hospital. I administer several systems and have my hands in most of the databases. Outside of work, I consult and write healthcare software.

You store it the same as you would any sensitive information -- behind a locked door with a ridiculous amount of audit data. It's more about identifying improper access (nurse A looking at patient B when she's not in his "circle of care") than it is about preventing it, for legitimate users of course.

You do not need to encrypt the contents of the database or any such extreme measures.

Something else to remember is that there is no bulletproof "HIPAA-Compliant" stamp. It's more a set of guidelines and best practices that you're trying to follow. Most vendors do not provide a row-by-row audit table for every single action, for example, but they should.