If you're not planning on installing an electrical panel in the garage, the installation is quite straight forward. You can basically treat the garage circuit, just like any other branch circuit. If you do plan on installing a panel in the garage, the following information is not for you.

Overview

You'll install a 20 ampere breaker, in the panel in the house. From there you can either go straight into conduit, or you can run any other approved cable. From the question, it sounds like you want to use nonmetallic sheathed cable from the panel, which is just fine. You'll connect the 12/2 with ground NM cable appropriately in the panel, and run it out to a junction box near where the conduit will leave the house.

Then you'll run conduit from that junction box, outside, underground, then up and into the garage, ending at another junction box. You'll want to make sure you install expansion fittings where appropriate, especially if you're entering the buildings above ground.

Next you'll pull three, 12 AWG THWN wires through the conduit. Connect the wires from the NM cable, to the THWN conductors in the junction box in the house.

Finally, you'll run cable from the junction box to the outlets in the garage.

Single, or Multi-wire branch circuit

National Electrical Code allows a garage to be supplied by a single, or multi-wire branch circuit without much trouble. If you don't plan on using much power, and don't mind having the lights and receptacles on the same circuit. You can simply run a single circuit out to the garage, and power everything with it. However, if you want to separate the lighting load from the receptacles load, you can install a multi-wire branch circuit without much extra effort.

If you decide to install a multi-wire branch circuit, you'll have to install a double pole breaker instead of a single pole breaker. So to do this, you'll have to have two slots open in the panel. You'll also have to install an additional conductor, so you'll have to use 12/3 NM cable and pull and extra wire through the conduit.

Conduit Size

Whether you decide to install a single or multi-wire branch circuit, you'll need to use at least 1/2" conduit if you're using schedule 80 PVC. According to Table 5 of Chapter 9 of the National Electrical Code, each 12 AWG THWN conductor has an approximate area of 0.0133 in.². Table 4 of the same chapter, says that 1/2" schedule 80 PVC has a total internal area of 0.217 in.². However, since there are more than 2 wires in the conduit, you can only fill the conduit to 40%.

0.0133 in.² * 3 conductors = 0.0399 in.²
0.217 in.² * 0.40 = 0.0868 in.²

Three 12 AWG THWN conductors will take up 0.0399 in.², while 40% of the total internal area of 1/2" schedule 80 PVC is 0.0868 in.². So there's no problem fitting the 3 conductors through the conduit.

0.0133 in.² * 4 conductors = 0.0532 in.²

Even if you decide to run a multi-wire branch circuit, you'll still have plenty of room in the 1/2" conduit.

Conduit Minimum Cover

According to Table 300.5 of the National Electrical Code, direct burial nonmetallic raceways not encased in concrete or other raceways is required to have a minimum cover of 18" (450 mm). However, if it's a residential branch circuit, 120 volts or less, GFCI protected, with 20 ampere or less overcurrent protection, it can have a minimum cover of 12".

So if you're installing a single branch circuit to supply the garage, you can install a GFCI breaker and you'll only have to bury the conduit 12". Otherwise, you're going to have to bury the conduit 18".

NOTE: Minimum cover is based on the conduit running under nothing but grass and dirt. Minimum cover may vary if run under concrete, walkways, streets, parking lots, etc.

Grounding and Bonding

Since you'll only be installing a single or multi-wire branch circuit, you'll only be required to run an appropriately sized grounding conductor along with the current carrying conductors (250.32(A)Ex. 1). You'll extend this grounding conductor to each outlet, and connect any devices to it. There are no other grounding or bonding requirements, as long as there are no metallic pathways connecting the two structures.

Means of disconnect

As Speedy Petey points out, you'll also need a means of disconnect inside or outside the building near where the circuit enters (225.31, 225.32). A means of disconnect is simply any approved method of disconnecting all ungrounded conductors. This could be simple snap switches, a pullout disconnect, a safety switch, etc.

Outlets required

Once you supply a garage with electric power, you'll also have to install a few required outlets. First you'll need at least one receptacle outlet (210.52(G)(1)), which will have to be GFCI protected (210.8(A)(2)). You'll also have to install one switch controlled lighting outlet inside (210.70(A)(2)(a)), and one switch controlled lighting outlet on the outside to provide lighting for the entrance/exits (210.70(A)(2)(b)).

^{Single branch circuit supplying garage}

^{Multi-wire branch circuit supplying garage}

Notes:

• This answer is based on National Electrical Code 2014, and may not be applicable to areas that do not follow NEC.

I quite agree, pulling three 4/0 Al wires is the kind of job a DIYer ends up getting stuck on and having to call an electrician just for his truck full of pulling tools.

How old is this work? If it was legal to wire ungrounded at the time, it may be legal to retrofit ground using the NEC rules allowed for that. For a retrofit, the rules are liberalized and you have a much wider set of choices for how to get it done. Make that argument to the AHJ and see what they say.

Also, why dig a wnole 'nother trench? You only need to dig out the old trench to the 45, which I assume is only a few feet from the house and shed. Then you can disconnect the wires, cut the pipe (carefully) and get the access you need to get the ground wire through. If the joints were not cemented, it'd be even easier. Really keeping an underground conduit watertight is a lost cause, it will fill up with water, that's why the wire has a THWN rating. So not cementing it does make sense. It's exactly what I'd do in that circumstance.

Also, if your wire is the obsolete AA-1350 type, just be careful with your terminations, make sure the lugs are made of aluminum (most are), use the anti-ox and torque them exactly to spec. I see no reason to spend a fortune on new AA-8000 wire, they both conduct electricity just fine, the issue was always at the terminations, and even that was mainly an issue for the tiny wires (10-12 AWG) on Cu terminations. On the other hand if the old wire is not outdoor rated, that's a different kettle of fish.