I've seen some conflicting information on this, but here is my understanding.
Vaccinations are considered medicines by the IRS. Here is what IRS Pub 501 has to say about medicines:
You can include in medical expenses amounts you pay for prescribed medicines and drugs. A prescribed drug is one that requires a prescription by a doctor for its use by an individual. You can also include amounts you pay for insulin. Except for insulin, you can't include in medical expenses amounts you pay for a drug that isn't prescribed.
In order for medicines to be deductible (and eligible for HSA medical expenses), it needs to be prescribed by a doctor. If you are getting the vaccination from your doctor's office, it should be eligible for the HSA. If you are walking into the pharmacy without a prescription and getting a vaccination (as is commonly done for a flu shot, for example), it is not eligible for the HSA.