brand new travellers to japan

my husband and I (50's) have never been to Japan.. and want to have 2 weeks next year around April. I want to see history, culture, countryside, cherry blossoms and local crafts. John is into martial arts and wants to follow his "roots" in Okinawa. Any suggestions on how, when, where and who with would be appreciated...especially accommodation, tours, packages etc. Thanks Anne

The cherry blossoms pin you down to around early April:
http://www.japan-guide.com/e/e2011.html

For first timers, I recommend Tokyo and Kyoto.

An ideal route would be:

enter through Tokyo - (air) - Okinawa - (air) - Kyoto - leave through Osaka

Here is a good general starting point for your research:
http://www.japan-guide.com/e/e623.html

If you want to see Tokyo's history(From Edo Shogunate period to modern Tokyo), visit to Edo-Tokyo-Museum.

http://www.edo-tokyo-museum.or.jp/english/index.html

Best tip is to travel light and enjoy the moment! You're in Japan, everyone is efficient and polite.

Enjoy the authentic Japanese foods and fruits in season.

Experience an onsen bath, it will do you good!

Have a fun and memorable trip!