the “Department of Redundancy Department” is a jocular name for a fictitious government department. Many newspapers had a “Redundancy Department” that featured redundant speech. “Our Own Redundancy Dept.” was in a 1956 newspaper, criticizing “perfect ideal.” “Redundancy Department” was in a 1968 newspaper, criticizing an announcer who asked fans to “stand and rise for the National Anthem.”
 
The Firesign Theatre coined “Department of Redundancy Department” in its comedy sketch “Don’t Crush that Dwarf, Hand Me the Pliers” (1970).
 
     
TV Tropes
Department of Redundancy Department
(...)
The Firesign Theatre gets credit for naming this trope on their classic 1970 album “Don’t Crush That Dwarf, Hand Me the Pliers”, the album where the trope name comes from.
       
11 January 1956, Waterloo (IA) Daily Courier, “Strictly Personal” by Sydney J. Harris, pg. 4, col. 2:
Our Own Redundancy Dept. was suggested last week by Governor Stratton of Illinois, who, in a speech, assailed the people who expect a “perfect ideal.”
 
14 May 1962, Arcadia (CA) Tribune, Lyle W. Nash column, pg. 14, col. 1:
THE Redundancy Dept.: No one expects a “perfect ideal” candidate.
 
23 June 1968, Waterloo (IA) Daily Courier, “Street Scene,” sec. 2, pg. 13, col. 2:
Redundancy Department
The Iowa City athletic announcer who asked fans to “stand and rise for the National Anthem.”
 
OCLC WorldCat record
Don’t crush that dwarf, hand me the pliers
Author: Firesign Theatre (Performing group)
Publisher: New York : Columbia, [©1970]
Edition/Format: Musical cassette : Cassette recording : No Linguistic Content
 
16 April 1971, Daily Northwestern (Evansville, IL), “A test for those who know” by Phil Lentz, pg. 4, col. 3:
The Associated Student Government is: a) the name of President Strotz’s pet cat, b) a local in the AFL-CIO, c) Student Senate in disguise, or d) the Department of Redundancy Department.
 
Google Books
The Firesign Theatre’s Big Book of Plays
By Firesign Theatre (Performing group)
San Francisco, CA: Straight Arrow Books
1973 (1972)
Pg. ?:
Your food, housing, insecurity will be guaranteed by your Department of Redundancy Department, and the Natural Guard. mudhead:
 
27 August 1976, Seattle (WA) Times, “Flesh eaters and flesh mortifiers” by John Hartl, Tempo, pg. 2, col. 2:
“THE RETURN OF A MAN Called Horse,” at the Cinerama Theater, belongs to what the Firesign Theater used to call the Department of Redundancy Department. Rarely has a sequel seemed more repetitious or less necessary.
 
Google Books
The How To Go To College Book:
Hundreds of Specific Techniques to Make College Easier
By Michael J. Gross
Seattle, WA: Passage
1978
Pg. 84:
Most writers can make the most startling advances in their writing simply by working to eliminate their Department of Redundancy Department.
     
Google News Archive
5 October 1981, St. Petersburg (FL) Times, “Great Majority Of Public Input Mandates Viable Word Usage: by Sally Jacobsen (AP), pg. 3A, col. 2:
And a federal employee in Dallas said: “Thank you for trying to rid the federal government of the Department of Redundancy Department.”
 
YouTube
Don’t Crush that Dwarf, Hand me the Pliers. PT 3
graybeard1952
Uploaded on Jun 7, 2008
Firesign Theater
(“Department of Redundancy Department” is at about 8:45.—ed.)
 
Language Log
The department of redundancy department
September 26, 2010 @ 1:37 pm · Filed by Geoffrey K. Pullum under Humor
Years ago, I once saw a sign on a psycholinguist’s door saying ‘DEPARTMENT OF REDUNDANCY DEPARTMENT’, and I smiled at the joke. But today I happened to notice that the Jersey City corporate seal says ‘CITY OF JERSEY CITY’, and the city website is cityofjerseycity.com; I assume I am not meant to smile at that.