We are going to Japan in the beginning of April and we are looking for good accommodation in Tokyo and Kyoto for two adults and two teenagers. We would like interesting options that take us into the Japanese culture as far as possible. As hippietrail points out below we are not looking to get specific hotel recommendations but rather what kind of accommodations there is on the table. I saw - for example - somewhere that there are hot spring inns. That sounds really interesting. And if there are monasteries welcoming visitors would be really cool too.
Your question is a little confusing. You're asking about staying in Tokyo, but there are no hot spring inns ("ryokan," as others have already pointed out) that I know of in Tokyo. In Tokyo, your best bet for an authentic Japanese experience would probably be one of the guesthouses.
You could, however, find ryokan in Kyoto, although that city is not particularly famous for its hot springs.
If you want good ryokan near Tokyo, I would recommend the resort town of Hakone near Mt. Fuji. There are many ryokan of various price levels to be found there, many with their own private hot spring baths. It's a little touristy, but targeted at the Japanese, not foreigners.
I also like Nikko, which is located in the mountains on the other side of Tokyo and features several famous temples.
And if you're the adventurous type, I would go so far as recommending Kusatsu (Gunma prefecture, NOT Shiga), a small resort town in the mountains. They have several "famous" public hot spring baths ("onsen") there, and it is one of the best memories I have of Japan after living there for a year. It's not as easy to get to as the others tho. Some Japanese friends took us there; all I remember is we took a high-speed train from Tokyo's Ueno station, then a local bus for a few miles after that. But it is definitely worth the trouble if you have the time.
Finally, I would recommend using one of the many travel agencies located all over Tokyo. I don't know if you know this, but tourism is a BIG business in Japan, and there are travel agencies all over the place, usually at the train stations. They offer discounted package deals for places all over Japan (and the world) with great service (service is also kind of a big deal in the Land of the Rising Sun). I would imagine that the agencies at one of the major subway stations (like Shibuya, Shinjuku, or Tokyo station) would speak English, and they can make your reservations, and book your train tickets and everything else you need.
Hope that helps, sorry to be so long-winded, but Japan is one of my favorite places... :-)
In Tokyo I can recommend hotel new koyo. But this is my personal suggestion, so we could differ on taste. As an alternative you can try places.google.com. Or reading the suggestions given on booking.com
For the truly cultural Japanese accommodation experience you need to stay in a traditional Japanese inn, called a "ryokan", but they are not cheap.
A cheaper option which won't be as traditional but will give you more cultural immersion than a hotel is to stay in a modern Japanese guesthouse. I stayed in a great one in Osaka a few months ago and most nights there would be Japanese visitors or the hosts would prepare us Japanese food. There are sure to be such places in Tokyo and Kyoto too.