“Deck the halls with matzo balls” is a parody on the “Deck the halls with boughs of holly” winter carol. The matzo ball joke has been printed on many images.
 
“Deck them halls with matso balls” was printed on Christmas cards in 1956.
 
       
Wikipedia: Deck the Halls
“Deck the Halls” or “Deck the Hall” (which is the original version of the lyrics) is a traditional Christmas, yuletide, and New Years’ carol. The melody is Welsh dating back to the sixteenth century, and belongs to a winter carol, “Nos Galan”, while the English lyrics, written by the Scottish musician Thomas Oliphant, date to 1862.
             
Wikipedia: Matzah ball
Matzah balls (Yiddish: קניידלעך‎ kneydlekh pl., singular קניידל kneydl; with numerous other transliterations) or matzo balls are Ashkenazi Jewish soup dumplings made from a mixture of matzah meal, eggs, water, and a fat, such as oil, margarine, or chicken fat. Matzah balls are traditionally served in chicken soup and are a staple food on the Jewish holiday of Passover.
   
13 December 1956, San Francisco (CA) Examiner, “Baghdad-by-the-Bay” by Herb Caen, sec. 2, pg. 1, col. 1:
The crazy Christmas cards are around again. Frexample: “Deck Them Halls With Matzo Balls!”
 
23 December 1960, The Wisconsin Jewish Chronicle (Milwaukee, WI), “Greeting Cards Run Wild,” pg. 6, col. 5:
One such card became the target for a bit of over-zealous police action in December, 1957. Washington, D. C., police closed up a stationery shop for selling a Christmas card featuring a woman holding up a string of tinseled balls, and the legend: “Deck them halls with Matzoh balls.” Police officials complained that the card was a “satire on the Holy Holiday.”

20 July 1963, The Morning Call (Allentown, PA), pg. 15, col. 7 ad:
Deck the Halls with Matza Balls
(Kulowich’s restaurant.—ed.)
   
4 January 1978, The Arizona Republic (Phoenix, AZ), “Holiday parties may have summer reruns” by Dorothee, pg. K26, col. 2:
Her invitation had said: “Deck the halls with matzah balls,” but with luminarias lighting the path directly to the margaritas, the parody soon changed to “Deck the halls with hot tamales.”
 
Google Groups: alt.music.filk
Pagan Yule Carols
.(JavaScript must be enabled to view this email address)
11/24/92
I’ll look about and see if I can find a copy of “Deck the HAlls with Matzo Balls.” Of course it isn’t exactly pagan…:) 
 
Twitter
shel israel
@shelisrael
Posting my annual Holiday blog http://bit.ly/5ii5 has had a cathartic effect on me. Think I’ll deck the halls with Matzoh balls tonight.
7:08 PM - 12 Dec 2008
 
Twitter
Lynda Wilson
@flysilly
Deck the halls with matzo balls, fa la la la laaaaaa!  #fb
8:24 PM - 2 Dec 2010
   
Twitter
Lauren Grossfeld
@Not_Lauren
“deck the halls with matzo balls” -guy yelling outside.
10:15 AM - 28 Dec 2010
   
Twitter
Mandy
@NJTeach151
It really is the little things in life, like finding a candle holder in @HomeGoods that says, “Deck the Halls with Matzoh Balls”. You know I bought it. 😆
4:45 PM - 4 Nov 2018
   
Twitter
SignYourName
@signyournamenet
It’s time to deck the halls with matzah balls! HAPPY HANUKKAH! #HappyHanukkah #Hanukkah #Hanukkah2018 #Hannukah
2:31 PM - 3 Dec 2018
 
Elite Daily
23 Best Captions For Hanukkah 2018 That Your Instagram Will Love A Latke
BY MARISA CASCIANO
December 4, 2018
(...)
5. “Deck the halls with matzo balls.”