There's a few more details here than other versions, but others are worth the read.
The original industructable is here. Check this site, though, for the granddaddy of tire sandal pages,though.
Step 1: Cut the tire
I used a reciprocating saw to start with. Keep pouring water on the tire to make it easier to cut. Most tires have metal bands on the insides--you'll have to cut these out first.
Use the saw to cut across the tire first, then cut the bands out. If you get a wide truck tire, I recommend cutting the sidewalls off too--they get in the way and you'll have to cut them off anyway.
Make a pattern using a shoe that you like--make sure you've got plenty of room on the sides of your feet--you'll need 1/8-1/4" later.
Cut off a piece of the tire a bit larger than your pattern.