These high level Japanese Kaiseki restaurants are usually called "Ryotei". They can be found in large numbers in upscale entertainment areas (Ginza etc.). Reservations are a must and preferably you will go with a fluent Japanese speaker as chances are no-one will speak English! The restaurants are inhabited by politicos and business people on expense accounts (thus the introductions another OP talked about). You can expect to spend 50,000 yen and up at these establishments. Might I suggest (if time allows) heading off to a smaller city/town to try a Ryotei , the price will certainly be cheaper and food quality ought to be better!