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 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 
- 2 D-rings or, my preference, triangle shapes
- 1 yd of nylon strap of a width to fit your triangles 
- 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.
 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!