Step 1: The part where you get the tire
Get the tire. This is as easy as going to any roadside auto body shop. They'd give you 200 if you wanted. Preferably the tire should be relatively thin and worn out. Put it in the trunk of car, and spend a moment feeling really cool. You're about to make the coolest pair of footware on the planet.
Step 2: The part where you cut the tire
Cut the tire, using a circular saw, hand saw, etc. Whatever cutting implement is available, although I would advise against attempting to get it done with a hacksaw or steak knife. First, cut it in half. Then cut the sides of the tire off, such that you have a strip making up the surface tread, the part that usually comes in contact with the roadway. This is the only part that's suitable for making shoes.
Then, take measurements of your foot, to make a stencil. I just traced my foot on a piece of cardboard. Feel free to be as elaborate as you feel is necessary. Put the stencil on the tire, lining the heel and toe up with the axis of the tire. Knock yourself out and cut to your heart's content.
Step 3:The part where you labor for hours and hours
Get some leather from a used clothing store. Material from leather jackets, old clothes, etc, work really well. Using a pair of pliers, start stitching at the toe, pressing the needle at each stroke through the leather and then at a 45 degree angle with the tire (sole). This is the easiest way I found to get around the problem of how to attach the leather to the shoe. Glue doesn't reliably work, at all.
The rest of the stitching needs to be done by eye. Use strong thread, for sure, and use the pair of shoes you're currently wearing as a model. (Note: ans has written up a model for an open sandle on this shell. I decided to go for the covered top, mostly as a challenge. It was very time consuming, but worth it. Do not fear, both types will yield the coolest pair of footware, ever.)
Step 4: Cool tag things
Make a tag inside the tongue of your shoe, saying who made it and what size it is. Your shoes could be size 1. Or size 7. Or size 0010011. Who's going to tell you what size they are? We have now discovered the coolest thing, ever, with the aid of a walkthrough about how to make shoes out of a rubber tire.