You say that all of your music is on your Mac. Is it all in one library, or do you have separate iTunes libraries.
If they are separate then it will be complicated, as using one iTunes match account will result in all the libraries being made available, which could be quite messy.
If the music is all in one iTunes library then it is quite easy. Just sign up to Match on your Mac and let it get on with matching and uploading to the cloud. Then turn match on on each persons devices. There is a limit of 10 devices which can be used, and the Mac is counted as one of them.
If you have individual iCloud accounts then that won't affect things as it is a separate thing, but if you have different iTunes accounts that you purchase music on then this may cause some problems with matching, as songs only show up as purchased if they were bought on the same iTunes account as that which you use to sign up to Match.
Hope that makes sense.
You have to be in range of wifi or 3G to stream from the cloud. Using Match, you can download tracks to be stored on the devices, and the sensible solution if you are likely to be away from internet access at times is to have a playlist of your favourite stuff downloaded for offline listening, but you can access the rest when you are online.
A couple of things to consider:
If your 3G data is capped you may run into problems if you stream a lot.
When you play songs on your phone then it does actually download the song as well. This is handy if you play the song again as it doesn't need to redownload, but you will need to do some regular housekeeping to ensure that you don't fill the device up.