This is how I make Naruto sandals. It isn't as easy as cutting up a sock and pulling it over your sandal, but I think it looks a lot better. I find this method really inexpensive and simple, though you will need to know how to use a sewing machine (or find someone who can help you). This is the result:
To start, you will need 5 pieces of equipment:
1. Sharp pair of scissors
2. Sewing machine with a heavy-duty needle
3. High-temperature Hot Glue Gun (I use a cheap $1.99 model from Wal-Mart)
4. Fabric pencil or colored pencil to mark cloth
5. Sewing pins
These are the materials you will need:
1. 1/2 yard of cotton duck in the color of your choice. Though, if your feet are bigger, it's a good idea to go ahead and buy 3/4 yard of fabric to allow for extra room.
2. Thread to match (I'm using button-hole thread because it's strong, but All-Purpose is good enough)
3. High-temp glue sticks
4. Cheap pair of flip-flops
5. Upholstery tacks to use while assembling the shoe
A note on fabric: Cotton Duck is a strong cotton fabric usually used for outdoor stuff. You can find it at JoAnn fabrics in the section where they keep the upholstery and outdoor fabrics. It is rather stiff, and of very heavy weight, which makes it hard to cut and sew sometimes. I use it because it is very durable and looks more like shoe canvas, but I'm sure lighter fabrics would also work, if you find yourself intimidated by working with such heavy stuff. A good alternative is to ask the clerk to help you find a "bottomweight fabric with a little stretch," a cotton blend with 2-5% spandex is a good option because the extra give will compensate a little for a better fit and make getting into and out of the shoe easier. Also, the cotton duck I use is about 54 inches wide (if I remember correctly) so if the fabric you want to use is narrower, buy more to compensate for lack of width.
Optional materials include:
1. Fabric paint to change the color of the flip-flops (it's darn-hard to find royal-blue flip-flops)
2. Upholstery Tacks painted the same color as your fabric for anchoring the shoe to the sole (not really necessary, as I've found hot glue alone works just fine, but extra security can't hurt)
The first step is to cut the thong off your flip-flops* and paint them the right color if needed.
*if making Sand-Village Sandals, do not cut off the thong and see notes on special Sand-Village Style construction
Cut your piece of fabric in half, parallel to the short sides. Take one piece of your fabric and fold it in half, making a rectangle and place it on a solid surface.* Put your foot on the fabric as shown, so that your ankle bone rests roughly in the center and your foot is parallel to the longer side of the fabric.
*When you cut the length of fabric in half (which is originally 24" long [for 3/4 yd] by 60" wide) each piece should be 24" long by 30" wide. Then, you fold the pieces in half to get two layers for the two halves of each shoe. The final rectangles, when folded in half, should measure 24" long by 15" wide.
Keeping your foot at 90 degree angle as much as possible, use your pencil to trace the top of your foot from your toes back to about 3-4" up your ankle.