The best way to get there is probably by train - Fiesch is on the railway from Brig to Andermatt. All the timetables for Swiss trains are available online - you can print out a personalised timetable showing all the connections, and even the platform numbers.
There is a cable car (Luftseilbahn) from Fiesch up to Kuhboden, which is perched on the mountain above the village. There are fantastic walks from here. From the next stop on the railway line, you can get another cable car up to Bellwald, from where there are beautiful views down over the Valais, towards the Matterhorn.
The village itself is beautiful, as is all the surrounding area.
There are lots of well-signed footpaths in the area, but it is worth consulting the local tourist office, as some of the paths can turn very tricky without any warning. An easier possibility would be to catch the train up the valley (into the 'Goms') get off at any of the stops up to Oberwald, and then walk back. Munster, half way up the Goms, would be another good place to get off the train - the old wooden houses are worth seeing in their own right.
Catch the cable car to Kuhboden and walk back to Bettmeralp for more stupendous views, and call in at the Alpina restaurant/cafe for refreshments in Bettmeralp. If the weather is good you could continue the footpath down to Riederalp, and then back through the Aletsch Forest, with views of the giant Aletschgletscher. Another incredible fair weather round walk from Kuhboden would be to the Marjelensee - a torch would be useful, as the shorter route is through a tunnel. You can catch another cable car from Kuhboden up to the summit of the Eggishorn, with views over the Aletschgletscher towards the Jungfrau.
A short, but hair-raising, bus ride to Binn would also be an interesting holiday experience - the bus seems to be clinging to a ledge a lot of the way. It will bring you to the Binntal Landscape Park, a nature reserve known for both its natural and cultural landscape.
The station hotel has some very nice, reasonably priced, rooms. The trains don't run at night, so you should get a good night's sleep. The rooms at the back have a beautiful view over the village, and the ones at the front a nice view of the little red trains. Probably best to avoid a Friday night, when the local youths congregate noisily in the streets half the night - and you won't get any sleep.
There is a YHA in the "Sport Ferien Resort Fiesch" complex on the outskirts of the village. The centre is rather lacking in charm, but the low price, good location and free access to the facilities make up for it.
- Camping Eggishorn is a very nice camping to stay. From here, it's only 5 minutes walking to the FiescherAlp shutlle lift.
If you are driving, and the weather is good, try the local passes - the Furka Pass, Grimsel, Gotthard, Nufenen, Simplon, and even the Susten, are all possible for a day out (not all on the same day!). To make a round trip, you could go over the Grimsel to Interlaken, and back through the Lotschberg car-train tunnel. All the views are incredible (except in the tunnel).
Travelling by train, Zermatt is a comfortable day trip, and you would have time to go up the Gornergrat rack railway, to see the Matterhorn up close. Another round day trip by rail would be to go up to Andermatt, down through incredible twisting tunnels to Goschenen, to catch a fast train to Locarno, then across the Centovalli line to Domodossola, and back via Brig. Although part of this is in Italy, you can use a Swiss Rail Pass on these lines.