És un baixista, compositor i líder de banda de jazz estatunidenc. Està casat amb la pianista i cantant de jazz brasilera Eliane Elias. 

El 1978, Johnson es va unir al pianista Bill Evans en el que seria l’últim trio d’Evans. Johnson va fer gires i va gravar amb Evans fins a la mort del pianista el 1980. El 2007 va publicar l’àlbum d’homenatge Something For You juntament amb la seva dona, la pianista Eliane Elias.

Des de llavors, ha publicat àlbums amb el millor del panorama jazzístic. També ha aparegut com a líder de les seves pròpies bandes, començant amb Bass Desires, un quartet que incloïa Bill Frisell i John Scofield a la guitarra elèctrica, amb Peter Erskine a la bateria, que va obtenir reconeixement internacional després de dos enregistraments d’ECM a mitjans dels anys vuitanta.

El seu llançament d’ECM Shades of Jade va aparèixer al número 5 CDs That Really Swing de Time del 17 d’octubre de 2005, com un dels cinc millors llançaments de jazz de la temporada. Va ser seleccionat pel Chicago Tribune com un dels deu millors enregistraments de jazz del 2005 i també va rebre el Premi de Música Danesa al Millor Llançament Estranger el 2005.