I've made several duffel bags for various purposes over the years. This one is the culmination of all the knowledge I've gained. It will hold all the things you truly need in any circumstance, make its way through any airport to your side, resist stains and abrasions, stop global warming, and cure cancer. It is perfect. (Its name is Tommy.)

This is not a beginner sewing project, but it's not extremely advanced either. You should have some experience using a sewing machine and knowledge of sewing terms like 'seam allowance' and 'presser foot' - or the willingness to look them up elsewhere!

Step 1: Tools & Materials

You'll need a tough fabric. Denim is good, or canvas; also many home decorator materials work well. A dark color will disguise the dirt the bag will inevitably accumulate, but some prefer the use to be visible: your choice. Definitely pick something that will be visibly different from other bags at a distance!

2 yd fabric (more or less, if you're making it REALLY big add another half yard)
3 yd 2" wide nylon strap [1]
1 24" zipper (or as long as you want the duffel to be)
2 8" zippers for the exterior pockets
2 12" zippers for the interior pockets
2 packets of double fold seam binding, one regular and one wide (I am actually using bias tape, but I'm using it AS seam binding and referring to it as such. Either will work)
sheet of flexible plastic - I cut the bottom out of an old laundry basket

for optional shoulder strap:

2 "swivel snap hooks" (see pic)
1.5 yd of nylon strap, of a width to fit your snap hooks [1]
2 D-rings or, my preference, triangle shapes
1 yd of nylon strap of a width to fit your triangles [1]
a little bit of padding: quilt batting, old blanket, etc.

The only tools needed are scissors and a sewing machine capable of handling your heavy fabric.

[1] Note that you may end up with nylon strap in three different sizes, or only one size; I used two sizes as my snap hooks took 2" strapping and my triangles took 1".

I used to have a nice picture of all the requisite pieces, but my camera ate it. Sorry!

Step 2: Cut Out the Pieces

The pieces consist of the list below. I haven't provided a pattern because they are all rectangles except for the ends, which are just roundish, as I'll explain below.

2 side pieces
2 bottom pieces (the bottom is double thickness)
4 end pieces (or 2, if you want to leave out the inside pockets)
2 side pocket pieces

The dimensions are up to you. I made this one on the small side both because I'll use it more often than a bigger one, and because my plastic reinforcement piece was small (the laundry basket was only 10 x 17 at the bottom). Adjust the measurements up (or down) as you like.

To cut the end pieces, draw (directly on your fabric is fine, or on a piece of newspaper if you prefer) a straight line as long as the width of your plastic piece plus an inch for seam allowance. This will be the bottom. Now draw the sides and top as part of a circle, or other bulgy shape - I like to make it slightly triangular - at a size that looks like a good one for your needs. Measure the circumference at half an inch in from the edge (for seam allowance!) and write it down as you'll need to calculate the side piece sizes from it. Mine was about 40" (precision of an inch is plenty).

Using this circumference measurement and the size of the bottom plastic, if you have a restricting one, calculate the sizes of the fabric pieces to cut for the bottom and sides as follows.

For the bottom, your sewn measurement should be 1/4" greater all around than the plastic reinforcing piece, to account for its thickness. For me, this worked out to 10-1/2 x 17 inches (I cut the plastic a little shorter than I absolutely had to, by accident).

From my 40" circumference, I then subtracted the 10-1/2" for the bottom piece, and another 1/2" for the width of the zipper, to get a difference of 29". This distance comprises both sides, each of which must therefore have sewn dimensions of 14-1/2" x 17".

The handles will lay at about the thirds of the bag length, putting them about 6" apart. So that's the width of my side pocket pieces, which will be sewn between the handles. Accuracy in the width is less important here as the straps are 2" wide and will cover the edges.

The cut pieces should be one inch bigger in each direction than the sewing dimensions, for seam allowance. So my final cutting dimensions are these:

2 @ 11-1/2 x 18 (the bottom pieces, remember it's a double layer)
2 @ 15-1/2 x 18 (the sides)
2 @ 10 x 6 (the side pockets, which I just decided would be 10" tall based on eyeballing it)

Whew! Measure again to doublecheck yourself before you cut. Sewing as well as carpentry uses the advice "measure twice, cut once".

Step 3: Construct the Sides

Cut 4 squares about 3x3 out of extra fabric, laid out so the warp and weft run diagonally. These will reinforce the area where the handle straps attach to the bag. They do not have to be very precise.

Lay out each side piece upside down. Lay the handle reinforcement pieces about 2/3 of the way to the top and with their centers each 4" from the middle of the sides. Pin the corners down and then sew them down thoroughly, just stitching all over, back & forth. This will show on the front, but if your thread matches, it won't show much. I've used a contrasting thread just because I like it.

Sew seam binding over the edge of each of the side pocket pieces. Then sew to each one of the short zippers, with the zipper upside down as in the picture. Then fold the zipper up, and topstitch for strength. Pin the pocket & zipper to the side piece so the bottom of the pocket matches the bottom of the side, and the top corners are over your reinforced areas. Sew the other edge of the zipper to the side piece, going over it several times. Stitch the sides of the pocket down, you only have to do this once as the handle straps will go over those edges anyway.

Cut 2 pieces of the wide nylon strap, each about 48 - 60" long depending on your bag size, for the handle straps. Before you cut, pin the strapping down and hold it up imagining the completed bag, so you don't make the handles too long or short.

Lay the cut straps out along the sides of the pocket with the ends at the bottom of the side. Make sure the part that will form the handle isn't twisted. Sew these down very solidly, from the bottom up to a few inches past the pocket, ending within the reinforced area. Pay special attention to these top areas as that's where most of the strain will be. I like to sew big X's.

Finally, sew seam binding around the top edges of each side, where you'll attach the zipper next.

Step 4: Sew the Main Zipper

Cut a couple pieces of scrap fabric about 2" x 2". Wrap one around each end of the zipper, tucking the ends in, and sew it down. The point of this is to give the zipper something to butt up against before it hits the end pieces. It's easier to construct this way and less likely to tear.

Now pin the zipper to the top of one side piece, right sides together, and stitch. Fold the side piece down and topstitch for strength. Attach the other side similarly.

If you'll be checking this through as baggage on an airplane, you can make a little loop at the end of the zipper where the zipper pull is when closed, to lock it to. It won't keep anyone out, but it will make it immediately obvious if it's been opened, and prevent the zipper from opening accidentally. Cut a small piece of fabric about 2" x 1". Fold the long edges towards the middle, then fold the whole thing in half, tucking the raw edges inside, and sew along the length. Then fold it in half and stitch it to the zipper pull end of the zipper as shown in the picture.

Step 5: Construct the Ends

Take two of the end pieces and cut a slice off near the top. Bind each edge, and sew the 12" zipper into the slice, so the piece when done is the same size as before, but zips apart in the middle. The zipper insertion is pretty much just like the main zipper insertion but easier as there's not so much extra fabric to deal with. You may find that the ends with the zippers and the ends without are slightly different sizes now; just trim them to match.

If you're making a shoulder strap, now is the time to add the part it will hook to. Take one of your D-rings (or triangle rings) and feed about 4" of the nylon strap through it. Fold this back on itself and pin the strap, short side down, to the center of the end piece, on the outside. The D-ring should sit an inch or two below the top of the end piece. Sew this all down thoroughly, and cut the strap off at the bottom of the fabric. My pictures don't exactly match this because I did the next bit first, before I remembered I wanted shoulder straps, so I sewed these on from inside the pockets... not recommended!

Now you're ready to construct the inside pockets. Lay one zipper'd piece on top of one of the uncut end pieces, wrong sides together (so the shoulder strap bits are NOT in between). Stitch all the way around the edges - this will get sewn again so you don't need to go over it more than once. You may find that the zippered pieces are no longer the same size as the others. That's fine - just trim to fit.

Step 6: Construct the Bottom

Next up is the bottom. Place the two bottom pieces together, wrong sides together, and stitch the two long edges using a half inch seam allowance. This is the only place where the seam allowance needs to be accurate (otherwise you'll end up unpicking the seam, or cutting extra off your bottom plastic!).

Insert the plastic reinforcement to be sure it fits with a small amount of ease. Then take it out again; you'll sew three of the four remaining seams without the stiffness of the plastic impeding you.

If you haven't already, make sure the edges and corners of the plastic are reasonably smooth without roughness that might abrade the fabric and wear through unseasonably.

Sew each side of the bottom to one of the sides, being careful to stitch along the seam lines you already sewed on the bottom pieces. It doesn't really matter which side of the bottom pieces you sew to, but for the sides, make sure the right side is facing the bottom pieces. Using the wider seam binding, bind the seams.

Step 7: Put It All Together

The next two seams are the only bits that are difficult to sew. You must stitch the round end pieces onto the straight ends of the combined side/bottom. Lots of pins are helpful here - make sure you're pinning the right side of the body piece to the side of the end with the triangle and strap. The duffel will look completely inside out at this point. If you find when you pin, that you have extra length in the side/bottom edge, try using a smaller seam allowance (geometers will see why this is). If you have extra length on the ends, try using a larger seam allowance.

For me, it's usually easier to have the curved part on top and the straight part underneath, but you may find the opposite. Once you've sewn the seam, go around again; then bind it using the wider seam allowance.

Now you have one end done. Before doing the last end, open the top zipper halfway or so, if it's closed - they're hard to unzip from the underneath and you're going to close off your access to the zipper pull.

You still don't quite need to slip the plastic piece in yet; you can put it off a little longer. Pin the other end piece the same way as the first, but only sew the areas where the side pieces go. Sew them twice. Also bind this area, starting near one of the bottom corners and leaving a tail of seam binding long enough to finish. NOW you can slip in the plastic piece and sew up the last seam (twice). And bind.

Turn the bag right-side out through the main zipper. Your duffel is complete! Admire it!

Step 8: Construct Shoulder Strap (optional)

Cut a piece of strapping of an appropriate length for a shoulder strap - try it on to work out the best length. With a candle, lighter, match, gas stove, or other heat source, melt the ends of the strap ever so slightly, to keep them from fraying. Push each end through a swivel hook and stitch it down solidly. (To make an adjustable strap, you need an additional slider part; I find I never need to adjust straps but the once so I never bother with this.)

You can also make a pad to ease your shoulder when carrying heavy things. You'll need something to be the padding - part of an old quilted jacket, a blanket, a piece of foam, anything squishy should do. Cut three oval pieces of your fabric about 6" long and an inch or so wider than your strap. Also cut one or two pieces of your padding a half inch smaller all round - enough padding to be enough, basically.

Cut the rounded ends off one of the three fabric pieces, fold down the short ends and stitch. This will be the bit that holds the strap to the padding. Now make a sandwich of all the parts, in this order:

1 fabric oval, right side down
all the padding
1 fabric oval, right side up
the non-oval, right side up

Stitch together around the edge, and bind the edges. Slip the strap through. Clip the strap onto the bag, adjust the padding to your shoulder. Carry something around!