I've decided to make one from this nice dotted canvas fabric, and I love it! It would probably work well with any heavy weight fabric, or you could use a light weight fabric, but make it double sided - possibly with a different color inside. You can prepare a strap from the same fabric, or use a pre-made one. While the second option is much faster and easier, preparing your own strap might be very pretty for some fabrics.
Step 1: Marking The Fabric
Strap: 98 cm (you'd better measure yourself to make sure it's comfortable)
Bag: 32x37 cm. Leave 2-3 cm on the sides for seem allowances, and about 3 cm on the top for the hem.
Due to the fabric's pattern, I've decided to mark it on the right side, with a light colored chalk. This way I was able to make sure the dots will come out as I'd like them to.
Step 2: Preparing The Strap
Anyway, I pinned the entire strap just the way I wanted it to be, and then I made two stitches - one on each edge (in case you never done it before - you can sew on the pins, no need to remove them). First stitch for the hem, second stitch to flatten and shape the strap on the other side.