At what point during the course of treatment of a new patient should notice of use and disclosure of health information, required under HIPAA, be given?

At the very beginning ... while filling out all those forms, and definitely before being seen by any doctor.