Nearly every car stereo system has four speakers situated roughly at the corners of the car, so it's an obvious environment for surround sound -- and, indeed, back in the 8-track era, several manufacturers produced in-car Quad-8 players. I think it's time for a quad revival.
These days, most car stereos have CD players, some kind of digital audio processing engine, and four separate power amplifiers, which means it should cost next to nothing to add support for decoding surround sound. There are a number of formats that could be supported.
SQ and QS are simple matrixed encodings, used on many quadraphonic LPs in the 1970s. In some cases, the CD releases of these recordings kept the surround information intact; Mike Oldfield's "Hergest Ridge" is one example. Dolby Surround and Pro Logic are more recent matrix systems, and have already been implemented in some car stereos.
Compressed surround sound, using DTS, AC3 and similar codecs, has been available in various consumer products for years. The "5.1 Music Disc" format from the late 90s used standard audio CDs containing DTS rather than PCM audio; few titles are available in the format, but since they're as cheap to produce as a normal CD they're still available and relatively inexpensive.
The compressed-audio decoders present in many car stereos present a new option for "compatible surround" CDs: store the front channels as regular CD audio tracks, and the rear channels as MP3 or similar files on data tracks. You'd have to read the surround data into a buffer first, but you can probably get away with relatively low bitrates for the rear speakers.
There are also a number of schemes for simulating surround sound from a two-channel recording. The classic Hafler circuit (feeding the back speakers with the difference between the front speakers) is trivial to implement. Many surround amps use delays or reverbs to synthesise a rear channel.