Until the 1660’s, the Dutch colony of New Netherland originally stretched approximately from the Delaware River to the Connecticut River, encompassing what is now New York, New Jersey and part of Connecticut, though there was conflict between English and Dutch settlements (and their respective rulers) in what is now Connecticut and on Long Island.
In March 1664, James Stuart, Duke of York, brother of King Charles II, was made proprietor of the territory between the Delaware and Connecticut Rivers (plus some other territories), an area that was controlled by Dutch. York dispatched Colonel Richard Nicolls, four frigates and about two thousand troops to what was then New Amsterdam, arriving August 26 and disembarking troops in “Breuckelen” and Staten Island. After a bit of a stand-off, and a promise by Col. Nicholls guaranteeing “every man in his Estate, life and liberty,” the Dutch surrendered on September 8, 1664. Col. Nicholls declared that both the colony and the city would be known as New York.
In 1665, the Duke of York gave the portion of the colony between the Hudson and the Delaware to John Lord Berkeley and Sir George Carteret, who called the new colony New Jersey. The boundaries of what became New Jersey and what remained in New York were most likely contained in the deed of grant from York to Berkeley and Carteret, though I don’t know the details of it. I would suspect that State Island was retained in New York because it was already developed for agriculture and economically part of the regional economy of the City of New York.
In 1664, the City of New York was on the lower tip of Manhattan, and from there grew up the island, eventually crossing onto the mainland into part of what is now known as the Bronx. The City of Brooklyn developed across the East River from lower Manhattan, and eventually absorbed the other towns that comprised Kings County. North and east of Brooklyn were another group of town (plus Long Island City) in what is now known as Queens. Staten Island (Richmond County) was also had a number of towns which were increasingly interdependent with New York City.
In 1898, all of Manhattan, Brooklyn, Queens, Staten Island and what is now the Bronx (having pulled some further land away from Westchester County) were joined together into greater New York City. If you want further details about municipal consolidation, ask stuyguy, our resident expert on the consolidation, and its protaganist, Andrew Haswell Green.
[source: Edwin G. Burrows & Mike Wallace, Gotham: A History of New York City to 1898, Oxford University Press, 1999]