I'm back home now from my travels and my bag is all finished. It really was easy to make -- knit all in one piece and fit conveniently in my carry-on while I was working on it. I actually stashed my working yarn in the bag as it began to take shape.
To begin, I cast 36 sts onto 10 1/2 needles and knit in the garter st for about 16 rows. (ok, nothing is ever exact with me, most of my measures are approximates! But I give you these as guidelines to construct what you want in your own size.) Switching to circular needles I picked up sts around the edges of the rectangle (16, 36, 16) placed a marker in between each group and then joined them and knit in the round for about 8". Then I switched to a different color and knit for and inch.
To shape the handles I continued to knit in the round, binding off the 16 sts between markers on each of the sides. With a separate pair of same size needles I continued knitting up the front and then later did the back. After knitting another inch I bound off 15 sts in the center of the row and then cast them on again in the next row to shape a very large button-hole like handle. When felting this comes out looking way neater than it did in the floppy stockingette stitch.
I repeated the same for the back of the bag and when I got home and threw in my laundry (jeans and sweatshirts are best) I tossed in the bag for 2 cycles.