After deciding for sure on a location and size, and testing out the plan by stacking up some blocks, we started by digging a shallow (6") trench for a poured concrete foundation. I built forms from 2x4 material that were exactly the outside dimensions of the finished wall, and we filled them with 12 bags of concrete, sticking pieces of rebar in at some locations where the web holes in the block would be.
Ready for concrete
This isn't a "real" foundation, like you'd build for a house or other serious structure. It doesn't go deep enough, and doesn't have enough rebar, but I think it will be fine for this project.
The finished foundation
The next day, I mixed up a bag of type-S mortar and built the wall from 6 x 8 x 16 concrete blocks. I'd carefully laid out the orientation and spacing before even digging the foundation, so it went pretty quick. Basically I just buttered everything up with mortar, set a block in place, and tapped it into position with a chunk of 2x4 until it was level and plumb, being especially careful with the corners and ends. I scraped off any squeeze out as I went, and used it for the next block.
All mortared together
We then filled some of the empty cavities with concrete (all the re-bar containing ones and a few others in structural spots) and filled any gaps with mortar.
Filling the cells
Jackie then applied a skim coat of mortar to the entire outside face, and textured it with a plastic broom so that it matches the texture of our house's foundation.