Brief synopsis.
Any bachelor's degree major will do. If you want to teach long-term, get a degree related to EFL, and some certification (that thingamajig).
How do you get here? Two options:
1) Apply to the few places that come to your country to interview, or to the even fewer that offer phone interviews (shudder).
2) Put US$4000-5000 in your pocket and come during a good hiring time (Feb/Mar) and be prepared to set yourself up and survive for 2-3 months without a paycheck.
Entry level work will be JET programme ALT, dispatch company ALT (more shudder), or conversation school (eikaiwa).
After a year, do something else that will net you better money and reputation.
This is a very brief explanation! Read the FAQ and internal links, then come back with some specific bazillion questions, or go to the ESL Cafe and read the 4 stickies called FAQs in the Japan discussion forum there before coming with questions.