It's an allusion to the Wise Men of Gotham, an old (at least 16th C) English folk story as to the supposed stupidity of the inhabitants of the eponymous village. In brief, the tale revolves around a village that decided to avoid hosting a passing king by acting stupidly. Through carrying out nonsensical tasks - such as attempting to drown an eel or building a wall around a cuckoo to stop it flying away - they convinced the king that they were a village of fools and thus best avoided.
In this sense the tale of Gotham was passed down with two meanings: a place full of idiots and fools and a shrewd display of cunning. It was the first that saw the label applied to the supposedly pompous and self-absorbed New Yorkers and the second that led them to adopt the nickname.
As a note though, it wasn't an Englishman that first attached it to New York but rather a Manhattanite, the famous Washington Irving. His journal Salmagundi first uses the term in 1807 to skewer his fellow citizens, mocking their airs. Other cities might boast ancient traditions (Trojan refugees seemingly having nothing better to do than found famous cities) but New York, claimed Irving, was the 'renowned and ancient city of Gotham', the city of fools.
(Irving had history, pun intended, in this form of mock-history. His History of New York similarly played fast-and-loose with the murkiness of the city's history, popularising the term Knickerbocker in the process.)
In terms of sources, the story of the Wise Men is common enough and Irving's writings are available online. Most of the above however is derived from Burrows and Wallace's excellent and aptly named Gotham.
Something wrong with this post? Let us know!