Did anyone ever notice that NJ secondary CR 539 goes through NJ almost in a straight line. From Tuckerton to Allentown it is due north and south almost and in a straight line. Plus it is in line with CR 533 in Lawrence, NJ east of Trenton further to the north of Allentown.
In Lawrence, NJ CR 533 is locally called Province Line Road as well. Back way before Washington was born, NJ was two separate colonies. There was East and West Jersey and if I remember correctly the boundary between the two was across on a narrow angle. Coincidence? I think not.
These two routes in line I think must of been that boundary and the name in Lawrence was for that.
Province Line Road has some other pieces as well as you get up toward Trenton, some of which are county-maintained, others are town-maintained. Of course you're correct - it's actually the Ocean County line that marks the old border, and pre-Mercer County, it was obvious all the way up to the Delaware from county lines alone.
There's also another surveyed border (don't remember if it's older or newer) that follows Ocean CR 640.
Holy crap, The Story of New Jersey's Civil Boundaries, 1606-1968 (http://www.state.nj.us/dep/njgs/enviroed/oldpubs/bulletin67.pdf) (10.5 MB PDF) is scanned online. It has information about the old East-West Jersey border and what still follows it.