According to one web site:
"The first Labor Day holiday was celebrated on Tuesday, September 5, 1882, in New York City, in accordance with the plans of the Central Labor Union. The Central Labor Union held its second Labor Day holiday just a year later, on September 5, l883. In l884 the first Monday in September was selected as the holiday, as originally proposed, and the Central Labor Union urged similar organizations in other cities to follow the example of New York and celebrate a "workingmen's holiday" on that date."
In 1894, Congress passed a law declaring the first Monday in September to be Labor Day.
(OXFORD ENGLISH DICTIONARY)
Labour Day U.S., a legal holiday observed on the first Monday of September; a similar holiday observed in Australia, New Zealand, and elsewhere
1886 N.Y. Times 7 Sept. 8/1 (heading) How *Labor Day was observed by all classes of workmen.
1887 Westm. Gaz. 6 Sept. 7/1 An Act passed last winter by the State Legislature, making the first Monday in September a legal holiday, to be called 'Labour Day'.
1910 World Almanac (N.Y.) 30 An act [of 1893-4] making Labor Day a public holiday in the District of Columbia.
1931 Daily Express 2 Sept. 1/5 The governing committee of the New York Stock Exchange, in response to requests of members, decided to close on Saturday, and also to close on Monday, on account of Labour Day, and to resume on Tuesday.
1963 Times 26 Feb. 9/1 The city's [sc. Melbourne's] big retail stores invented this affair, which has taken over the traditional public holiday called Labour Day, now in any case a quaint anachronism in a country of trade union strength.
1974 Anderson (S. Carolina) Independent 23 Apr. 1B/1 This is a drastic change from present and past school calendars which start several days prior to Labor Day and finish earlier in the spring.
12 June 1880, Fort Wayne (IN) Daily News, pg. 5, col. 2:
FOR THE PARADE.
The Formation and Line of March
for Labor Day.
The grand marshals for the Labor Day parade met last night and arranged for the line of march and its formation.
26 March 1886, Keystone Courier (Cornellsville, PA), pg. 3, col. 2:
Not a New Holiday at all.
A crank in the New York legislature wants September 1st made a legal holiday, to be known as Labor Day. Around this office we observe six days of the week as labor days, and if legislators would follow our example they would earn their salaries.