There are many questions to answer before you get started:
Will you take a large group 15+? Will you limit numbers to less than 10? Will you travel before or after the homestay? Will you attend school? How do you arrange all of this? Can you do it on your own or do you need help? These 2 documents from the NZAJLT website will help with your initial planning:
Katrina Martell's Advice
Kazue Takeda's Advice (日本語)

Should you use a company that organises school trips to help with all or part of the trip?
Educational Travel International (ETI)
Roy Vaughan from ETI on the question of personal and school liability
New Zealand Institute of International Understanding (NZIIU)

Should you use a local travel agent or go directly to group booking at Air New Zealand?
Air New Zealand Group Booking

Can you approach local councils with sister-city relationships to set up homestays?
New Zealand - Japan Sister Cities

This site of Japanese schools was recommended to try to find a sister school. Choose an area and then choose a type of school. A dark green square means the school is interested in an exchange programme. Although this doesn't necessarily mean an international exchange, it might be worth a letter of introduction. You might get lucky!
Search for a Sister School

Or start with homestay possiblities here:
Homestay in Japan

Post-Trip to Japan Survey A Few New Additions!
50 New Zealand school groups who traveled to Japan in 2007-2009, did so in a variety of ways. Some information they reported back on was: time of year; length of the overall trip, number of participants, homestay locations and high school visits; and places of interest they visited. Also check out the updated Accomodation Page for their recommendations on hostels and hotels.

This NSW Department of Education and Training website has many useful documents.
Planning a Trip to Japan Link Fixed!

Here are a few more documents you'll need to get started:

Application for your Board of Trustees approval
Sample #1 (Judith Hoek), Sample #2 (Eric Lindblom)

RAMS Forms (Risk Analysis and Management System)
Sample #1 (Eric Lindblom)

Crisis Management Plan
Sample #1 (Eric Lindblom)
Emergency Telephone Numbers Card (Eric Lindblom)

Student Application
Sample #1 (Eric Lindblom), Sample #2 (Judith Hoek)
Medical Consent Form / Health Form (Christine Parnell)
Student List Template (Eric Lindblom)

Student Profile Form
Sample #1 (Anne Jacques), Sample #2 (Helen McEwen), Sample #3 (Nobuko Watanabe)

Student Code of Conduct
Sample #1 (Helen McEwen), Sample #2 (Eric Lindblom)

Setting a Budget
Sample #1 (Nobuko Watanabe), Sample #2 (Eric Lindblom), Sample #3 (Aukje Both)

Itineraries - January
January Itinerary - (Ian Forlong) - January - Tokyo -> Osaka (homestay) -> Kyoto

Itineraries - April
April Itinerary - Christine Parnell
Itinerary with some costs - Christine Parnell
Rotorua Lakes High School (Heather Richardson) - Kyoto -> Hiroshima -> Kyushu (homestay) -> Osaka
Rosehill College (Robyn Rensen) - Kyoto -> Osaka -> Hiroshima -> Gunma (homestay)
Lytton High School (Shingo Suematsu) - Kyoto -> Osaka -> Ishikawa (homestay) -> Aichi (homestay)
Fiordland College (Shona Salomen) - Narita (homestay) -> Aomori -> Hokkaido (homestay)
Sancta Maria College (Amara Kevern) - Tokyo (homestay) -> Hiroshima -> Kyoto
Sancta Maria College (Amara Kevern) - Tokyo (homestay) -> Hiroshima -> Kyoto (More Detail)
Diocesan School for Girls (Susan Marriott) - Tokyo (homestay) -> Kyoto
St. Andrew’s College (Virginia Simcock) - Tokyo -> Kyoto -> Hiroshima -> Fukuoka

Itineraries - September
Itinerary and budget - (Christine Parnell) - September - Osaka (homestay) -> Hiroshima -> Kyoto -> Tokyo
Itinerary with some costs - (Christine Parnell)
Itinerary Sample (Eric Lindblom) - September - Tokyo -> Fuji -> Kyoto -> Hokkaido (homestay)
Rail Itinerary Sample (Eric Lindblom) - September - Hiroshima -> Kyoto -> Fuji -> Tokyo -> Hokkaido (homestay)
HS Itinerary sample (Eric Lindblom)
Itinerary Presentation (Helen McEwen) - September - Saitama (homestay)-> Hiroshima -> Kyoto
Kaipara College (Akiko Maruno) - Aichi (homestay) -> Tokyo -> Osaka
St. Matthew’s Collegiate School (Junko Bracefield) - Chiba (homestay) - Tokyo -> Takayama -> Kyoto -> Hiroshima
Linwood College (Ross Marwick) - Kyoto -> Hiroshima -> Tokyo (homestay)
Southland Girls High School (Ainslee Woodward) - Saitama (homestay) -> Hiroshima -> Kyoto
Edgewater College (Wendy Sheahan) - Tokyo (homestay) -> Kyoto -> Hiroshima -> Osaka
Mt Roskill Grammar School (Yukiko Kojima) - Tokyo -> Gifu (homestay) -> Kyoto
Long Bay College (Nobuko Watanabe) - Tokyo -> Saitama (homestay)

Travellers' Cheques, Cash, Credit Cards, Bank Cards - Although credit cards are becoming more and more widely acceptable, cash is still king in Japan. Opinions vary on the use of travellers' cheques. Some people have found it hard to find banks which would cash them in large amounts. Some people don't like the long wait. Here are some comments from the NZJNET mailing List. There are a few international ATMs in larger cities, but bank cards with a Cirrus mark can be used in all post office ATMs.

Trip Booklets - usually include itinerary, advice, useful language, packing checklists, emergency procedures, code of conduct, task sheets, questions to answer about experience, local information, host family interview, diary pages, NZ National Anthem
Sample #1 (Publisher version - Catherine Linnen), Sample #1 (Word version - text only) 
Sample #2 (Christine Parnell)
Sample #3 (Helen McEwen)
Sample #4 (Publisher version - Nobuko Watanabe), Sample #4 (Word version - text only)
Sample #5 (Petra Cavanagh)
Sample #6 (Adam Burden)
Four new Trip Booklets from Aukje Both, Koichi Tomita, Michelle Lodge and
Wayne Waller (Publisher Version) Wayne Waller (Word version - text only).
Advice for Students could be used as part of a booklet (Robyn Rensen)
New! Student Journal from St. John's College (Julie George)

Clothing/Packing Lists
Sample #1 (Catherine Linnen)
Sample #2 (Helen McEwen)
Sample #3 (Judith Hoek)
Sample #4 (with short gift giving tips - Eric Lindblom)
Sample #2 (Nobuko Watanabe)
Carry-on List (Catherine Linnen)
The Universal Packing List

Gift Giving Tips
Please submit your ideas

Cell phone rental / NZ cell phone use in Japan
Go Mobile cell phone rental service
Advice from one of the teachers:
If hiring more than one hire them all from the same company as you cannot always text if dealing with different companies. We went with Softbank Global Rental – they only take credit cards and debit that account when they check the activity after the phones have been returned. We found that you could not text internationally but could call internationally. New!
International Roaming : Telecom
International Roaming : Vodafone
Calling Cards : Telecom

Please submit any documents which you think might be helpful.