Prehistoric Origami
John Montroll, (c) 1989, Dover Publications; ISBN 0-486-26588-9
The book's models are ordered by increasing difficulty, roughly; similar critters, such as flying beasties, are grouped together. Each is folded from an uncut square. The book also contains a brief explanation of the symbols used to indicate various folds, several pages explaining basic folds and bases, and a page about "wet folding" technique by Rosalind Joyce. In addition, each critter's directions are preceded by a pronunciation guide and a brief (educational :-) description.
Here are the critters you learn to fold. ("Steps" is really the number of illustrations, not the total number of folds, which would have been more tedious to count. It's still a reasonable indicator of complexity, though.)