Bury water pipes, gas line, and electrical pipe
Materials selection

There are three materials that you can practically use for a buried potable water line: CPVC, PEX/PEX-AL-PEX, and copper.  Of these, PEX is the easiest to install, while copper is the most proven in-service, with CPVC being a middle ground.  While there is straight PVC that is used for utility water service lines, most PVC pipe readily available is DWV (drain-waste-vent) pipe that is not approved for potable water service.  (If you doubt me, Tables 605.3 &amp; 605.4 in the 2015 IPC refer to different standards than tables 702.1 and 702.2 regarding PVC pipe.)

As to the propane gas line, you must contact your gas supplier for acceptable materials.  If you can't get a response from them, Schedule 40 or heavier black iron with joint compounds labeled as suitable for all gasses always works.  (The Code approval for copper in gas applications depends on the amount of sulfur in the gas, and using plastic for gas lines requires lots of special work that renders it infeasible for anyone but a gas utility.  See NFPA 58 and NFPA 54, as well as the 2015 IFGC, for details.)

Last but not least, you'll want to lay conduit for the electric lines instead of a direct bury cable.  In a co-trench situation like this, I would use a nonmetallic, physical damage rated conduit such as Schedule 80 PVC or RTRC-XW.  Direct burial of metallic conduits is also possible, but offers little advantage over PVC given the issues with corrosion a buried metal conduit faces, unless you use red brass that is, which is extremely costly compared to PVC.

If you must use a direct bury cable, PVC jacketed MC-HL is recommended as it provides enhanced damage protection and leakage current control compared to a standard MC cable's interlocked armor, although it can be harder to find.  Do not bury an unjacketed metal-armored cable, or NM for that matter!

Trenching

The minimum trench depth for a gas line is 12", and the same is true for water lines where freezing is not a concern.  The electrical, though, must be deeper (either 18" or 24" deep), so that sets your trench depth.  Width is not critical save for being able to properly install the piping with due concern for expansion (especially for CPVC pipe and rigid nonmetallic conduits).

As always, make sure to excavate safely -- call your local One-Call or equivalent utility marking facility before you dig!