First off, I have a bench well tailored to viseless woodworking. I am not going to demonstrate any features exclusive to this bench. If you want to see how the Nicholson bench handles not having any vises, check out this video 

Holdfasts are the easiest way to hold something to your bench without vises. They can work on almost any bench surface. Just drill a 3/4" hole. If your top is less than 2" thick, glue a 2x4 under where you want the hole

They are also inexpensive. A pair from Gramercy tools is 35.00. These are excellent (and recommended) 

Planing boards.
 One of the primary tasks of a workbench. Here I have a planing stop. It's just a 2" square hole with a 2" piece of wood in it. It is located directly behind the leg so when force is applied to it, it won't rack. I can tap it up for thicker wood, tap it down for thinner stock, or tap it under the surface to get it out of the way

Directly across I have a dog hole and a bench dog. I use the Kreg bench dogs. I think these are great for benches without a traditional wagon vise. At 8 bucks for 4, they are hard to beat. Between the stop and the bench dog, I put a batten. In this case a piece of 1/2" plywood. 

This gives me a huge bearing surface. I can plane this board without it moving around - even though it isn't in a vise. As long as I am going with  the grain. So what happens if I need to go cross grain? 

The notched Batten (or doe's foot). This video shows it in use and is what convinced me I could get away without having vises. I am using a 20" long piece of 1/2" cherry plywood. You'll see a theme here. I like using plywood for jigs. It's flat, very stable, tough, and inexpensive. 

After ripping it to about 2.5" wide and squaring the ends, I am going to lay out the notch. I like the notch to be 45 degrees but off center. This gives me flexibility in where I position it on the bench in relation to holdfasts. I start in one corner and draw a 45 degree line

I make a mark 1/2" from the opposite corner

And strike a 45 degree mark from there until I intersect my first line.  I do this on both sides of the board

I mark the center with an awl

and get ready to drill a 1/8" hole. I am using a holdfast to keep the piece to the bench and drilling over a dog hole. I'm not concerned with tear out on the back side    

Hole drilled right where the lines intersect. Again, both sides of the board

Here I am getting ready to cut with the piece in a moxon vise. Yes, this is ironic using a vise in a viseless woodworking how-to, but holdling pieces vertically is essential for some operations and this vise can be used on any surface. It's really easy and inexpensive to make 

I carefully saw my lines to the hole I drilled

Done, I clean this up a bit with some sandpaper.

This is how it works. With the piece up against the planing stop, I bring the batten into the corner, and the holdfast holding down the batten. Now I can plane across the grain without the piece moving. Because there is no clamping pressure applied, when I want to work the other side, I can simply slide it toward me, flip it over, push it up against the batten, and I'm ready to go

This is why I drilled the hole. with rough lumber I rarely have a square edge. The hole will give me some clearance for shaggy and less than square surfaces.

So how about planing edges? Well the wedged birds mouth takes care of it. Here is some really nasty scrap 3/4" plywood. It's about 16" long. 

I mark a line about 3/4 offset form the center to the left. Note that I am left handed, this the fence will be on the right side.  

From that line I measure out 1 1/2" in each direction, and from those marks, lay out an 8 degree angle going back toward the center line

At the intersection, I mark with an awl    

and drill a 1" hole

I then rip following the center line to the hole

Then I rip along the angles. Now I have my 2 wedges. Try to make a cleaner cut than I did. The "waste" will be your wedges

I clean up the inside of the birds mouth with a rasp, and plane the edges of the wedge material 

Now I glue and screw the fence on the edge

This is how it works. I push my stock in as far as it goes. The hole drilled prevents things from splitting. Once it makes contact on both sides, I tap the wedges in on each side

You can see the wedges engaged here. This holds the board very securely. Even if you have a face vise or side vise, I would recommend doing this. The piece gets a lot more support and it's easier to plane it square. The first time you use this you'll think it sucks because when you finish the stroke, the back will lift up. However that is not the case. Another good thing about viseless woodworking is your bad techniques are instantly exposed. If the piece is lifting off the bench at the end of your stroke, you have too much pressure on the front of the plane.     

This also is ideal for longer pieces. No deadman to worry about, no flexing in the center because the piece is fully supported, and no pivoting out of a face vise. 

It rests right up against the planing stop and will easily accommodate pieces up to 2.5" thick. Any thicker than that an appliance like this isn't necessary, just the planing stop will work.