Steinberg played with Soul Coughing throughout the band's entire history, from 1992–2000. He also recorded and performed with guitarist Marc Ribot and appeared on William Shatner's 2004 second album Has Been. In 2001, Steinberg performed on stage with Neil Finn and Tim Finn, Eddie Vedder, Johnny Marr, Ed O'Brien, Phil Selway and others in a concert recorded on a DVD titled "7 Worlds Collide". Steinberg performed on the Dixie Chicks' "Accidents and Accusations" 2006 tour, and toured with k.d. lang during the Summer of 2007. Steinberg performed with Vanessa Carlton on The Tonight Show with Jay Leno October 11, 2007. He appeared again in 2009 with Neil Finn and friends for the second installment of 7 Worlds Collide playing alongside members of Radiohead and Wilco.
Steinberg has worked as a session musician periodically, playing electric bass and double bass on numerous albums, most recently contributing the bass tracks to the Fiona Apple album, The Idler Wheel... released in June 2012. He commenced touring with Fiona Apple as part of her backing band in March of 2012.
Steinberg made a brief appearance in the film Funny People, as the bassist in a band that Adam Sandler's character, a movie star, hired to jam with him.
He was born in New York City and grew up in Newton, Massachusetts, son (with brother Adam) of musicologist Michael Steinberg and fabric artist Jane Steinberg. Steinberg currently resides with two cats, Rupert and Little Charlie Onions, more commonly referred to as "House Bears".