A while back, I wrote a post on how to write an academic research statement. This is a follow-up post on how to write an academic teaching statement, and contains my thoughts on what makes for a good teaching statement when applying to computer science departments in US research universities.
Like I said about research statements, the teaching statement is not the most important part of your application package. In fact, for research universities, the teaching statement is probably the least important part. Nonetheless there are pitfalls that should be avoided, because a bad teaching statement can hurt your application. Being an ineffective teacher is grounds for not getting tenure at many schools, and schools don't like to hire faculty that they don't think can get tenure.
For reference, here is my teaching statement from when I went on the job market in Fall 2012. I want to emphasize a few points:
(1) Do not blather on and on about how much you LOVE teaching. No one wants to read this, just like no one wants to read in your grad school application about how you've loved computers since you were three years old. Stuff like this lacks substance and makes you seem immature.
(2) Keep it short. No one wants to read a long teaching statement, and long teaching statements are usually just fluffed up anyways. Just like for the research statement, optimize the wording to be as concise as possible. I'd recommend keeping the teaching statement to one page.
(3) List the courses and topics you can teach. Some faculty search committees like to explicitly see what courses you can teach, so this is an important thing to mention in the teaching statement. I typically like to list this at the very end of the teaching statement. I would recommend being somewhat open-minded about what courses you can teach. You can always negotiate these things later.
(4) Briefly list your credentials. I typically like to do this at the very beginning. You don't need anything flashy here, but you just can't count on your recommendation letters to talk about all of your teaching and mentorship experience.
(5) Have a teaching philosophy. No one is expecting you to know exactly how you'd like to teach your courses, but not having an explicit teaching philosophy of some kind can be an indicator of complete lack of preparation. For reference, this part took up the 2nd paragraph of my teaching statement. One strategy is to connect this part to prior teaching and mentoring experience, where you can talk about what teaching styles of have been successful for you.
(6) Say something meaningful about outreach and interdisciplinary education. Computer science and data science are quickly becoming vital enabling disciplines for virtually all scientific and engineering disciplines. Recognize this, and have some kind of plan for how you want to contribute to it, or why it matters to you.