Follow cthoyes fine step-by-step to get the basic sandal from a tire, but skip the tabs on the sides and back of the sole. You won't be needing them. You'll find it is much easier to cut out the sandal without the tabs for straps.
Step 2: Chisel the slits for your rubber strips and feed the strips through
I originally made a sandal with rubber tabs but I wasn't happy with how they wrapped around. Uncomfortable and unwieldy, at least on mine. Once you have the basic shape cut out, keep using your chisel to cut slits right through the sandal top to bottom where you want the straps to be. You'll have to cut some 1" wide and 4" long strips of rubber from the tire sidewall at the thinnest point, four per shoe. Feed the strips through the shoe and bend them around as shown.
Step 3: Wire the rubber strips to the nylon straps
I used thin steel wire as 'stitching' for the straps. Strong thread or monofilament could be used, I suppose. Because I fed the wire through by hand, I predrilled the holes through the rubber strips for the wires using a very small drill bit. The hole closes up but the wire can still be easily threaded through. Poke it through the nylon and pull the whole thing tight with needlenose pliers. Be sure to run the wires from the inside out. Even though you crimp the wires down into the rubber, no point in taking a chance on a painful wire poke in the side of the foot. This solution makes clean, nonbinding straps that look professional and hold on surprisingly well. I've been test driving mine for a couple of weeks and am really satisfied. Last pair of sandals I plan on owning. Have fun.