What are best practices for researching ancestors in Colonial America?

I believe my ancestor served in the Colonial Army and was stationed at the fort at Black Point (Scarborough, Maine) during King Philip's War (1675). He served under Captain Joshua Scottow. He is mentioned in Soldiers in King Philip’s War (Bodge, pp. 336–37) and York Deeds, Book IV (Fol. 22-23). So far I haven't been able to find any personal data (date of birth, date of death, spouse, etc) about this ancestor. I've searched Maine state and county records online with no results. I would love to hear from anyone who knows about researching this time period. My questions: Where would be the best place to search in Maine? Or, since Maine was a part of the Massachusetts Bay Colony at the time, should I search in Massachusetts for birth/marriage/death records? If so, where? I appreciate any advice you can give. Thank you.