A few things off the top of my head:
-If you have to go through the degree program to get a degree in education again (you might), there is indeed a period where you have to student teach, or "intern" as was mentioned earlier, and the teacher you do this for will evaluate you. If you do have to go though the degree program all over again, do some research first. Try to find the universities that started off as a "normal school." Despite the unappealing name, that was the name given to institutions that specialized in training teachers. Not surprisingly, those universities tend to be renowned for their teaching programs, and some are actually fairly inexpensive (I'm attending NAU, personally. Before it was called Northern Arizona University, it was founded as a normal school).
-Being CONVICTED of a felony will get you fired. Being accused will likely result only in a suspension until your guilt or innocence is proven in court. REPEATED accusations for the same crime, however, will likely get you fired because it's bad for the school's image. Just like if you worked for Microsoft and repeatedly mentioned to customers on the phone how you thought Microsoft's products were utter shit and that they'd be better off with Apple. It may not technically be a crime, but it's bad for the organization.
-Bachelor's degree will allow you to teach at the pre-school, elementary, and high school levels. Master's degree is required for college / university teaching.
-Becoming a state certified teacher, despite the implications of the title, is optional. It does, however, bump your salary up significantly.
-Depending on where you plan to teach, and at what level, there may be additional and varying requirements. You should also research where you want to teach: inner cities tend to pay more than isolated communities, but generally speaking you can think of it as "hazard pay."
-You can also apply through the US Department of Defense for their teaching program. A minimum of a 2 year committment is required, your pay is based on a military pay grade, but they'll usually provide you with transportation to the base you'll be teaching at (you'll be teaching the kids of enlisted men and women) and occasionally housing. This is also an -excellent- way to see the world.
-Teaching on a reservation is risky, because although the pay tends to be great (it's a federal job), the contract can include a provision that lets the government fire you at any time. From what my EDU 205 professor told me (who taught on a reservation at a private school, though some of her friends weren't so fortunate), that provision can and will be enforced without hesitation.