"Los Bastardos" contains samples from the BBC television series The Young Ones including Vyvyan shouting, "Shut up, you bastards!" as well as Rick saying, "You just called me a bastard, didn't you?" and "Mike, you bastard!"
The lyrics "sail the seas of cheese" later appeared in the song "DMV" which appeared on their next album Pork Soda.
A deluxe edition of the album was released on May 21, 2013. It is available in two six-panel Digipak configurations, each featuring the album’s new stereo mix on CD and the new 5.1 surround mix on Blu-ray or DVD, plus three exclusive, previously unreleased bonus tracks.” Claypool stated, “Musically, it holds up incredibly well. Sonically, it holds up fairly well. There’s some old-style reverbs that are a little bit syrupy. With modern technology, we can fix some of that stuff. But we don’t want to mess with it too much, because it is what it is. We want to fatten it up a little bit.”
Reviewing the album for Allmusic, Steve Huey contends that "Sailing the Seas of Cheese completely redefined the possibilities of the electric bass in rock music for those who'd never heard the group before." He describes the album as "mostly riff-driven, fleshing out their heavy metal roots with prog rock tricks from Rush and Frank Zappa, as well as the novelty side of Zappa's sense of humor." He notes that "the willful goofiness may alienate some listeners, but... it never detracts from the band's frequently stunning musicianship" and concludes that this album is "the tightest, most song-oriented representation of their jaw-dropping, one-of-a-kind style." Simon Reynolds reviews the album for Entertainment Weekly by describing Primus as "too self-consciously goofy for their own good, but their rubber-boned thrash-funk can be cartoonish fun."