Andrew Leach's answer has the OED's first quotations [parenthetically in 1884, and] in 1890. Their first quotation for "in good nick" is The English dialect dictionary from 1905.
Australia, 1880s
I found earlier uses in the Trove archive of Australian newspapers, the earliest in The Referee (Sydney, NSW, Thursday 13 January 1887):
Hutchens and Samuels.
(By "Shoespike.")
Next Monday Hutchens will run his first
match in Australia. Malone's was to have
been the first, but the aboriginal party
were found willing to risk a century, and
a match was quickly made. Samuels has
not had much time for preparation, but is
quietly doing work on the Agricultural
Ground. He looks if anything fine, and
not so strong and in such good "nick" as
when he won the Botany. As an aboriginal
Samuels is a first-rate runner, and about
the best of them. I question, however, if
he is class enought to stretch the world's
champion and anticipate Hutchens to
win comfortably. I may add I do not
expect even time to be broke.
It was used in other Australian newspapers in the late-1880s to describe sporting participants: wrestlers, racehorses, footballers, boxers rowers.
New Zealand, 1870s
However, it can be found earlier in New Zealand's archive of newspapers, Papers Past, and again in a sporting context. First in Sporting Notes by "Sinbad" in The Press (Volume XXIX, Issue 3973, 18 April 1878, Page 3), describing racehorses:
York, the representative of the Bay stable, is big enough and strong enough. Those who ought to know say he has plenty of pace, and will certainly be there or thereabouts at the finish. He is without doubt in good nick, and will have a good man on his back, so I think he will run into a place, and if either Natator or Merlin are out of it he may be labelled dangerous.
(The article also uses the similar phrase in good form.) In good nick shows up in many other editions of The Press and also The Obago Witness in the late-1870s, all applied to racehorses.
An origin?
Another meaning of the noun nick dates from 1824 and, according to the OED:
10. An instance of cross-breeding, esp. one which produces offspring of high quality. Cf. nick v.2 7b.
You could say of animals or racehorses, as in this from an 1870 Australian newspaper:
It is possible,
however, as the mare is a daughter of Melbourne, that
Stockowner may prove a good nick.
From the same article, as a verb:
I see that a certain sire and dam "nick" well, no
matter how wrong it may be for them to do so, as far as
the relationship of their families is concerned, I prefer
to trust to their progeny, rather than to thoso bred on a
correct theory without practical results.
So perhaps as the term for successfully crossed animals, specifically racehorses, was applied to racehorses generally in good form. This was then used for sportsmen in general before being used for anything in good condition, or conversely, as "in poor nick" for something in bad condition or form.