For an employee to be given a “pink slip” means that this employee is discharged from employment. “He had had a squabble with Ray, one of the outfielders, and this coupled with a sore arm and weakness at the bat, brought him the pink slip” was cited in an April 1904 baseball note about a discharged player. It’s not known if discharge notices were at one time pink, and in what industry this practice began. The earliest citations (1900s) appear, however, to be from baseball.
Wikipedia: Pink slip (employment)
Pink slip refers to the American practice, by a personnel department, of including a discharge notice in an employee’s pay envelope to notify the worker of his or her termination of employment or layoff. Receiving a “pink slip” has become a metaphor for the termination of employment in general. According to an article in The New York Times, the editors of the Random House Dictionary have dated the term to at least as early as 1910.
(Oxford English Dictionary)
pink slip, n.
A notice of rejection or dismissal, esp. from employment or office. Also fig.
1904 Typographical Jrnl. Jan. 67/1 A revise proof to correct is regarded as a cardinal sin, for a ‘pink slip’ is charged up against the delinquent, and a certain number of these means discharge.
1906 Atlanta Constit. 2 Apr. 8/2 There is nothing like a prospective pink slip to fill the brawny athlete with zest and ginger.
1923 N.Y. Times 7 Oct. 2/1 Getting the pink slip, being canceled, which notice comes on pink paper.
24 April 1904, Augusta (GA) Chronicle, “Baseball Chips,” sec. 2, pg. 3, col. 5:
Dan Gallagher has been released by Manager LaRocque. He had had a squabble with Ray, one of the outfielders, and this coupled with a sore arm and weakness at the bat, brought him the pink slip.
27 July 1904, The Evening Post (Charleston, SC), pg. 3, col. 2:
Kelar has been given a pink slip by manager Ashenback, entitling him to join any menagerie that cares to land him.
27 July 1905, Waterloo (IA) Daily Reporter, “Safe Hits,” pg. 7, col. 3:
Outfielder Wadding was handed his “pink slip” after the game by Manager Frisbee.
14 June 1907, The News and Courier (Charleston, SC), “The Columbia Base Ball Team,” pg. 4, col. 4:
But there comes a time when patience ceases to be a virtue, and therefore we protest against Columbia being imposed upon by Manning’s “pink-slipped” players of last season.
Covering the Look-in Corner
By Burt L. Standish
New York, NY: Barse & Hopkins
“And have Murphy hand me the pink slip tonight!”
(This book is about baseball—ed.)
OCLC WorldCat record
Pink slip blues : blues fox trot
Author: Porter Grainger; Ida Cox
Publisher: New York : Vocalion, 
Edition/Format: Music : 78 rpm : Blues : Jazz : Multiple forms : No Linguistic Content
15 February 1939, FLASH!, pg. 25, col. 1:
WPA OPTIMISM—That’s what we called it when we heard about the “PINK SLIPS” party the lads threw up in Harlem who had received their (Form 403) PINK SLIPS, which meant the end of their project jobs.
OCLC WorldCat record
A pink slip means you’re through.
Author: CARR FD
Edition/Format: Article : English
Publication: Hospitals, 1954 Feb; 28(2): 112-4
Database: From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine.
Tracing the origin of the pink slip
Marketplace for Thursday, April 9, 2009
SHEIDLOWER: Well, what happens is that we have evidence from around the turn of the last century in a number of different contexts where a pink slip is something critical in various ways. The very earliest example we have is where a pink slip is a note sent to a typographer indicating that he’s made a mistake. And if you got enough of them then you would be fired. Yet another intermediate one in 1905 where a pink slip is specifically a rejection letter from a magazine. So a writer would submit a story, and it would get a pink slip back, meaning that the story was rejected. So clearly there is something going on at around this time where pink slip is being used to refer to various kinds of rejection.
Ryssdal: Is it an Americanism? Or do they have the same thing in say the UK, or in Russia, or in India?
SHEIDLOWER: No, it is an Americanism. But one of the interesting things about it is that in other countries they have different colors to refer to dismissal from a job. So in Germany the expression is to get the blue letter. In the French military, you would be dismissed with a yellow paper, carte jaune.