Trenching and running power to outside shed
How deep do you want to trench?

You'll need 24" of cover for buried cable, or 18" for common/cheap conduit.  You can use exotic conduit called Rigid or IMC, which only requires 6" of cover but is more expensive.  

Use 1-1/4" or larger conduit.  That will future-proof you to 100A+.  In the meantime, the large size will make pulling much more DIYable.  DIYers often are stuck/defeated by hard pulls close to the limit for the pipe. That's when you must embarrasingly call the electrician. The correct wire for in-conduit use is THWN-2, better to avoid using cable in conduit because it makes the pulls much harder. 

#6 wire will suffice.  If your distance was over 115' there'd be an argument for going up to #4 to reduce voltage drop, but it's not a problem for you.  Do consider bumping up 2 sizes and using #4 aluminum AA-8000 wire, which has always been reasonable for feeder, and this is the new alloy.  

Grounds

You absolutely will need both a ground wire in your run, and grounding rods at the shed.  2 rods 8' long, at least 6' apart (more is better). If the conduit is metal IMC or Rigid, that serves as the ground wire.

Main panel

If your main panel is full, it's time to bite the bullet and either change the panel (ouch) or add a subpanel right there and offload 4 spaces worth of circuits to the new subpanel.  

Go big.  Go HUGE.    Many builders cheap out and leave you with a tiny panel, often that require "double stuff" breakers just to have enough breakers.  Get a large enough subpanel to have at least 44 spaces between main and sub, preferably more.  Don't let double-stuff breakers substitute for a real space, they can't anymore.  

If your old panel is Federal Pacific FPE, Zinsco, Pushmatic or other brand where finding AFCI breakers is hard, get at least 40 additional spaces and figure on this becoming your new main panel someday. If it is FPE or Zinsco, do that like your hair is on fire, or your house could be.

The new in-house subpanel does not need a main breaker (but it will if you upgrade it to main panel someday). The shed does, though it will only serve as a shutoff switch.   A decently large (spaces) subpanel will have a pretty big "main breaker"  That's OK, it is specifically allowed to be bigger than the breaker feeding it.  If your thought is "Make the local breaker the same size so it trips first", haha, that doesn't work! Breaker sequencing is a black art, and Murphy's Law guarantees it will never be satisfactory.  

If you have any thoughts toward future use of a generator, think about an in-house subpanel that is just for the circuits you want on generator. Siemens makes a very slick kit for $30 that lets you use two common $9 breakers as the generator interlock. That, and the price of a Siemens main-lug panel, is cheaper than most interlocks alone. 

You cannot reverse the line to the shed to use both as generator feed and as subpanel feed. To do that, you would have to "permanently" rewire both ends, although if you set it up right, this can take 5 minutes to change.  I do that kind of temporary permanent wiring all the time.