Origami is a skill that is extremely hard to master. This tutorial will attempt to turn a beginner into an expert, at least in folding cranes.

Since I'm assuming you know nothing about origami, I'll be explaining some of the basic terms used in this tutorial

Crease - a ridge created by applying pressure to a fold. The more pressure, the sharper the crease.
Edge - the flat side of a square
Corner - the point where two edges come together

You probably already know these terms, but it does not hurt to define them.

Supplies

One square piece of paper
Patience

Step 1: Creasing

Make a diagonal fold, crease, and unfold. Make another diagonal fold in the opposite direction, crease and unfold. Flip the paper over. Make a horizontal fold, crease and unfold. Then make a vertical fold, crease and unfold.

Step 2: Layered Square

This is the most difficult step to explain. Basically, you're trying to get all the corners down to the bottom. You will end up with a square that has one "open" side and two "layers".

Step-By-Step

Fold the left horizontal crease over the diagonal crease underneath it, aligning it with the vertical crease on the bottom half. Fold the right horizontal crease crease over the diagonal crease underneath it, aligning it with the vertical crease on the bottom half. Grab the corner of the remaining unfolded corner and align it with the bottom corner.

Note - The rest of this tutorial involves layers. The third picture shows the side of the square, which helps explain what I mean by layers.

Step 3: Kite

Place the open end of the square facing you. On the top layer, fold the two bottom edges in so they align with the center crease. This will form a kite shape. Flip over and repeat.

Note: Flip over the square horizontally (left to right) rather than vertically (top to bottom). The kite needs to be the same on each side.

Step 4: More Creasing

Fold the top point down and crease above the kite folds. Unfold, flip over, and repeat.

Step 5: Diamond

Undo the folds from Step 3 and 4. On the top layer, grab the bottom corner and pull it up. Your creases should be sharp enough that sides naturally start to fold over, forming a diamond. If they aren't, you'll need to put in a bit more work.

Here's the breakdown:

When pulling the corner up, it will fold over Step 4's crease. That's the middle of the diamond.
The paper will sometimes buckle in the middle while you try to pull it up. Push them out and you should be good.
The creases from Step 3 form the boundary of the sides. Fold those sides in to finish the diamond.
There should be a "split" at the bottom when your done with both sides. Basically, you should be able to move the bottom halves separately

Step 6: Second Kite

On the top layer, fold the bottom edges in, aligning them with the crease. Flip over and repeat.

Step 7: Book Fold

On the top layer, fold the right half over the left half. If you're having trouble envisioning this, think of it as turning the page of a book. Flip over and repeat.

Note: If you are more comfortable folding left to right, do it! The exact method doesn't matter, as long as you stay consistent. If you're having trouble repeating the fold, count the layers. After the first fold and flip, one side will have one layer, and the other will have three. Flip the top layer from the three onto the one.