Subsonic is a really efficient music streaming server. You can get a good overview of the possibilities from the main site http://www.subsonic.org/.
This server can stream your complete music library to any internet connected device, handling on-the-fly compression. A subsonic client is available on the Android market for all android devices.
The main specificity of streaming music to a mobile phone, is that it uses a 3G or even a Edge access, where the available bandwith is quite restricted. You then need to use a very efficient codec and a high compression ratio to remain compatible with the network capacity.
After doing few tests, I realised that Ogg Vorbis is very good at low bitrate. Using this open source codec, it is possible to keep a good music quality with a bitrate as low as 80 or 96 kbits.
This tutorial explains how to configure your Subsonic personnal server to stream your music to your android device thru your 3G data plan, using a 96kbits Ogg stream.