I know step #1 should be "talk to a lawyer", but I'd really like to understand as much as I possibly can beforehand.
It's not really that hard. Keep personal data secure when stored and encrypted when in transit.
It is usually a mistake to think of HIPAA as some sort of over-arching checklist of requirements such as encryption schemes.
Instead, your goal is to put together a privacy and compliance plan that meets the HIPAA Rule as well as state and local regulations, which sometimes are more specific or strict. I find that the best way to start is to think about how your service uses data, who are your users, and what are they doing with the data (sharing it with others, keeping track of it, submitting claims through your system, etc.). Once you've figured that out, use the flowchart on the HHS website to determine if you are a covered entity under the HIPAA rules: http://www.cms.hhs.gov/HIPAAGenInfo/Downloads/CoveredEntityc...
Once you've determined if you are a covered entity, you can narrow the parts of the Rule in which you need to become expert. Depending upon your business, you may determine that you are a healthcare clearinghouse, a provider, a payor, or not a covered entity at all. Each of these entities have specific requirements, and you'll need to work with these requirements as well as fill in details in your privacy plan so that you can act within the law and also be a good data steward for your users. If you are not a covered entity, you still may need to comply with some parts of the Rule because you are acting as a Business Associate (BA) of a covered entity. Or you may not be a business associate-Google Health for example does not consider itself to be a BA.
The HHS website (http://www.hhs.gov/ocr/privacy/hipaa/understanding/index.htm...) is a good place to start. After that, the HIPAA Rule is formally implemented in 45 CFR Part 160, and Subparts A and E of Part 164:
* http://www.access.gpo.gov/nara/cfr/waisidx_07/45cfr160_07.ht...
* http://www.access.gpo.gov/nara/cfr/waisidx_07/45cfr164_07.ht...
Privacy rules are just one of the complex parts of healthcare. This is a huge part of the economy, and a large amount of the inefficiency isn't because someone hasn't created a web service to streamline it. Healthcare data aren't like banking transactions-there is a complex vocabulary and making it machine readable has been a huge challenge and isn't anywhere near being solved. There are also many embedded interests (employees with jobs they don't want to lose as well as big companies with profit motives). The upside is that if you do something successful, you will improve the lives of many.
Best of luck with your venture, and get in touch with any questions (mscantland at innova-partners dot com).