Adding some additional details to Uji-san's already perfect answer. If your first destination from Shinjuku happens to be Yamanakako or Oshino, take the bus.
If you are first going to Kawaguchiko or Fujiyoshida, take the train. Normally, a JR Azusa or Kaiji express train (these are not as fast as the bullet train but very nice trains) will take you to Otsuki where you will change to the Fujikyu railway. (about 70minutes)
From Otsuki, a local Fujikyu train will take about an hour to Fujisan or Kawaguchiko station, and the Fujisan Express train about 45 minutes. If you take the Fujisan Express, make sure you pay the 100 yen additional charge (in addition to the 900 yen express fee) to get on the salon car. It's much nicer and usually not crowded. Several times during the winter, even on a Saturday, I had the whole car to myself. The train is a former JR special express train so it is old but a nicely built train with comfortable seating, and very uniquely designed with Mt. Fuji cartoons drawn all over the train. (On the verge of being weird, in fact).
If you opt for the normal train, Fujikyu has a couple of interesting trains that run on normal schedule. One is the Fuji Tozan Densha which is a new train with a modern retro design that has a very nice salon-like interior, a library, and a female attendant who not only sells goods on the train but will take your photographs and other service in general. They charge you 200 yen extra seating fee as they only sell as many tickets as the number of seats available on the train.
The other train is the Thomas Land train which will entertain kids if you have kids in your group as the whole train is decorated with Thomas the Tank Engine characters inside and out, and there is a special kid's driver seat with real instruments and levers set at both ends of the train that kids can take turns "driving" the train. No special charges on this train.
Both trains run only about two times a day each way and I don't think Fujukyu has an English website so check with your travel agent for the timetable.
Also, a couple of new attractions on Yamanakako are the Kaba bus (amphibious bus) that will drive right into the lake, or the venerable swan boat which was given a new (and nice) interior. Designed by the same designer who did the Fuji Tozan Densha, the boat has a kid's section with small seats, a couple of them with steering wheels for them to keep busy.
My other personal recommendations in the Fuji area are the Mt. Tenjo ropeway in Kawaguchiko (provided that the weather is clear) where you get the most spectacular view of the whole Mt. Fuji and its surroundings. Oshino Hakkai, which is hard to describe other than several very clean springs with some old style houses in the vicinity, which does not really sound appealing but it is a nice place and I personally like it. If you like to look at old shrines, etc., Sengen Jinja shrine in Fujiyoshida city which is very solemn and quiet and a different experience where you walk through the long path in the pine woods to the shrine, cross a small river into the shrine area which is built behind two diefied trees. Nothing fancy but its very Japanese. You can be of any religion to visit.
