Should I dig a separate trench for CAT5e wire to shed?
Same trench is fine. Use conduit, you may want to upgrade it later without re-trenching. Keep some space between the conduits, vertically, horizontally, or both.
Interference between 60 Hz power and 100+MHz ethernet is wildly overestimated by numerous people. Ethernet encoding is designed to ignore noise, and ethernet cabling is deign to reject noise so it does not get picked up, and the &quot;noise&quot; of a powerline is very, very much slower than what goes on in ethernet.
Still, the better bet for &quot;what goes in your conduit&quot; is fiber optics, but that's mostly because it provides total electrical isolation for your network equipment at both ends. It also happens to be immune to any electrical noise along the way, but that's far less likely to be a practical problem than you imagine, while side effects of thunderstorms are far more likely to be a practical problem with a wired connection.
Whatever cable you place should be &quot;wet-rated&quot; - for whatever reason, direct burial cable seems to be the most common wet-rated variant seen in ethernet, but put it in a conduit anyway. Outdoor conduits are defined as (and usually are) wet locations.