They would just download like normal. Alternatively, you might be able to set up a M3U playlist.
M3U's sometimes trick media players into playing mp3's while they are downloading. An M3U is simply a text file with the full URL of an MP3 in it, and then saved as whatever.m3u. You then make this file available (as a link). When a visitor clicks on the m3u file, their player will open, read the file, start downloading the mp3, and it will play while it downloads.
Sometimes this works better than just providing a direct link to a MP3.
If you were go to with a paid server, generally shared hosts don't allow streaming, and there's no way to install a streaming server since most hosts wont give you that kind of access to install stuff on their server (because it's a security risk).
Your best bet there is to try to find a web host that offers streaming (most don't, but if you look hard enough, you should be able to find a few). Another option is to pay for a server that gives you root access (a VPS or a dedicated server). A VPS will cost you around $20/mo. A dedicated will usually cost about $70/mo. If you decide to go this route, I would suggest getting a VPS from KnownHost.com. We've done business with them, and they are a great group of guys to work with. All of their packages include free semi-management (meaning you don't have to know how to manage a server, they do it for you). They will also install whatever software you want for free (as long as you give them a link to the instructions). So you could get a VPS, find a streaming server with instructions, and then give it to them and have them install it.
Good luck!