As far as I can tell all Haineses I'm familiar with originated in England and came across in the 17th Century. There are at least four bunches in these early years. There was a Richard Haines who came from Devon, England, and became a substantial estate owner in Virginia, or South Carolina. Another Richard Haines, as already noted, led a party of Quakers to, or actually toward Burlington Co., New Jersey. He himself didn't survive the voyage. There was also a Rev. Samuel Haines who established a bit of a dynasty in New Hampshire. Finally, closer to my own roots, Richard and William Haines made it to Salem, Massachusetts in maybe 1634 or so. They were from Bedfordshire (near London) England. My own ancester, James Haines, was a cooper who arrived in Salem in 1637. There is some possibility, but thin evidence, that he was related to Richard and William. James Haines moved to Southold, New York, on eastern Long Island in about 1650, and died soon thereafter.
There's also the possibility that your own Haineses came much later, but most likely from England. It's an English name, for sure. Also, there are connections with the rather larger Haynes clan.