A “shade tree barbecue” is an informal barbecue—not always under a shady tree, although that is the image. The Texas term (also used in other southern states) is cited since at least the 1990s.
 
The more well-known term “shade tree mechanic” dates to the 1920s.
     
 
Shade Tree BBQ
About Us
My wife Lisa and I live in Jasper Ga.
     
5 July 1996, Paris (TX) News, pg. 1, cols. 1-2:
That competition was won not by a costumed pair but by look-alikes—a husky bulldog named Gator and owner Jeff Sykes, a member of the Shade Tree Barbecue team.
   
Google Books
Legends of Texas Barbecue Cookbook
By Robb Walsh
San Francisco, CA; Chronicle Books
2002
Pg. 44:
You used to see barbecue trailers at shade-tree barbecue stands by the side of the road.
 
25 May 2007, Times Record News (Wichita Falls, TX), pg. 16, col. 1:
RED RIVER HARLEY DAVIDSON MEMORIAL DAY CONCERT
(...)
Shade Tree barbecue serving food.
   
Houston (TX) Press
Shade Tree Barbecue with Dewayne Pines
By Admin in Q, Robblog
Monday, Jun. 30 2008 @ 9:50AM
(...)
I love Texas shade tree barbecue—I think of it as culinary folk art. Sometimes the barbecue is terrible. But when it’s good, it can be very, very good. And on this particular Saturday afternoon in late June, Dewayne Pine’s brisket and ribs were sensational. – Robb Walsh
 
Houston (TX) Press
Timpson Texas BBQ Stand
By Robb Walsh
Jul. 9 2009 @ 10:00AM
(...)
Take my advice—never pass a shade-tree barbecue stand without stopping for a sandwich. If you’re not hungry now, it will come in handy later.