One of the difficulties facing teachers wanting to teach higher order thinking skills is knowing what they are.  Higher order thinking can be said to be 'complex thinking that requires effort and produces worthwhile outcomes'.  Most teachers recognise good thinking when they see it, but it is a very difficult thing to define, teach or measure.  The art of thinking is difficult to understand.  Thinking skills develop and cannot necessarily be directly taught.  What can be taught and encouraged, however, is a set of attitudes and dispositions which lead to the ability to think effectively. 

Some of these dispositions include:

The disposition to be broad and adventurous

The tendency to be open-minded, to explore alternative views; the ability to generate multiple options.

The disposition toward sustained intellectual curiosity

The tendency to wonder, probe, find problems, a zest for inquiry; an alertness for anomalies; the ability to observe closely and formulate questions.

The disposition to be planful and strategic

The drive to set goals, to make and execute plans, to envision outcomes; alertness to lack of direction; the ability to formulate goals and plans.

The disposition to be intellectually careful

The urge for precision, organization, thoroughness; an alertness to possible error or inaccuracy; the ability to process information precisely.

The disposition to seek and evaluate reasons

The tendency to question the given, to demand justification; an alertness to the need for evidence; the ability to weigh and assess reasons.

The disposition be metacognitive

The tendency to be aware of and monitor the flow of one's own thinking; alertness to complex thinking situations; the ability to exercise control of mental processes and to be reflective.

From Teaching Thinking Dispositions: From Transmission to Enculturation - Shari Tishman, Eileen Jay, and D. N. Perkins, Harvard University 1992

The sorts of things we can do in teaching to encourage and promote the development of thinking dispositions include:

Further Reading on Thinking Skills

Nesta Futurelab Series Report 2: Literature Review in Thinking Skills, Technology and Learning
http://www.nestafuturelab.org/research/reviews/ts01.htm 

The Delphi Report: Critical Thinking: A Statement of Expert Consensus for Purposes of Educational Assessment and Instruction http://www.insightassessment.com/pdf_files/DEXadobe.PDF 

Computers as Mindtools for Engaging Learners in Critical Thinking, Jonassen, Carr & Yueh, 1998 http://www.coe.missouri.edu/~jonassen/Mindtools.pdf 

Dave Jonassen's site has many links to articles and resources on mindtools and problem solving http://www.coe.missouri.edu/~jonassen/ 

TERC's Good Models of Teaching with Technology 

Works by Seymour Papert http://www.papert.org/works.html