How do I eliminate the "whooshing" sound of water running though pipes?
Make sure the shutoff valves at your toilet and sink are fully open.  Inadvertently leaving them partially closed can cause sounds like you describe.

EDIT: Just noticed you said "at every faucet and toilet in our house."  I'd still check all your shutoffs just to be sure, but also make sure you check the main shutoff valve for the whole house.