It is a relatively easy job. You would normally use 12-3 wire, which is a single cable that has three conductors (plus ground). Black is phase 1, red is phase 2, white is a neutral, the bare wire is ground. As noted above, you break off the tab between the two "hot" terminals on the outlet, so that the top and bottom outlets are fed by the two different phases (black and red). The tab on the neutral side is left in place, as one neutral wire is used for both circuits.
Here is a picture that I found in a quick Internet search. It says 14/3 (14-3), which is for 15 amp circuits. You would want 12-3 for 20 amp circuits. You would also want a 20 amp outlet, which can be used with a standard plug, or a 20 amp plug, that has a "sideways" neutral blade. See the second picture
This arrangement allows for the most efficient circuit and the least voltage drop. It effectively reduces the cable length in half because no current actually flows through the neutral cable when both phases are in balance (using the same amount of power).
You can only use 12-3 cable if each circuit is on a separate phase. If both circuits were on the same phase, the single neutral return wire would be severely overloaded, carrying the load from both circuits, 40 amps. In that case, you would use 12-2-2 cable, which has two neutral wires.