These tessellations are from "Origami Tessellations" by Eric Gjerde. It's a really impressive book with 25 different patterns, clear (although challenging) instructions, and advice on choosing the right paper.

"Star Puff" - on a 50cm hexagon of Lokta paper. Lokta is soft and really enjoyable to fold, but it's also stiff enough to hold the creases. I cheated by using a ruler and protractor to create the hexagon - I'm pretty sure folding would have been less accurate.

This is a really simple tessellation - the hexagon is folded into a grid of equilateral triangles, which are used to create 120° corners and hence several layers of stacked hexagons. These hexagons become equilateral triangles, which are puffed out from behind to create six-pointed stars, leaving the hexagonal holes on the reverse. The stars can be placed anywhere on the grid; the positions I chose continue the hexagonal theme.
  
"Propellerheads" - on a 70cm square of Elephant Hide. Elephant Hide is incredibly stiff and quite painful on the fingers, but it's well-suited to wet-folding which allows the curves to be shaped. 

The tesselation is based around interlocking waterbomb bases on a 16 by 16 square grid. Once all the creases are made, the bases can rise out of the paper simultaneously, before being twisted and locked into place.

"Chateau-Chinon" - on a 30cm square of Elephant Hide. This was a pretty frustrating experience - the entire pattern needs to be precreased, before the tessellation is slowly massaged into shape. Because of the way the reverse side locks into place (the small squares in particular), it's impossible to fold one section at a time. More hands would have been extremely useful.