Whether you cycle this road or secure your bike at the hostel/campground at Te Anau and catch a bus, is a matter of personal choice. You have to travel the same route twice, in and out again, and it can be arduous in parts, particularly the steep (900 meter) climb to the Homer Tunnel. The narrowness of the road, the frequent tour buses and the length and darkness of the long Homer Tunnel can be a bit daunting, although some touring cyclists have found this road particularly beautiful and worthwhile. There is a scattering of DOC campsites along the way, but no stores. Milford Sound itself has a hostel, campground and store. The Sounds themselves are however, spectacular.
Invercargill is New Zealand's southernmost city with pleasant folk, campsites, hostels, a fine museum, bike shops and a place to catch the ferry to Stewart Island. Stewart Island is indeed a real beauty spot and visitors love its isolation, beaches and pristine bush. It is not a great place for cycling, but if you are willing to swap your pedals for tramping boots for a bit, then this is a rewarding and worthwhile destination. Most cyclists however, head from Invercargill up toward Lake Manapouri and Lake Te Anau and the possibility of a trip to Milford Sound.
From Invercargill, pedal west to Riverton (38k) a sweet old New Zealand town with a folksy atmosphere and a touch of the alternatives. There is a camp site here, supermarket, tea rooms etc. This is a good spot for lunch, ice cream or to just mosey around a bit and imagine a bit of the history of the place. The following extract is from the Cyclopedia of New Zealand.
In the earlier times the streets of Riverton were frequently crowded with bullock-drays laden with wool, grain and other produce, which was shipped from the port. The scenery seen from South Riverton is very fine, and includes the waters of the estuary, with green hills relieved with small patches of pines and smiling homesteads, and, in the background, the timber-clad Longwood ranges, with the rugged ramparts of remoter mountains.
Further on, there are campsites at Colac Bay (10k out from Riverton, tea rooms, dairy, pub and hostel) and at Orepuki (28k out from Riverton, pub, camping in the domain). Tuatapere (47k out from Riverton) has a motor camp, store and tearooms. The road so far has been fairly flat, but from Tuatapere it begins to rise steeply over Jericho Hill (400 meters). It's a good 80k from Tuatapere to Manapouri so, depending on your fitness and commitment, you will want to break this journey up at some point.
The best thing about this route is that the road is fairly quiet, rural and scenic with a long stretch of road beside the coast. There are occasional interesting historic spots like the bridge at Clifden (60k from Riverton, DOC camping ground) and interesting side/return routes to remoter and beautiful areas like Lake Monowai (DOC camping, no store, hostel) or a fairly long side route (32k) to LakeHautoko (basic camping, no store). Lake Hautoko is notably New Zealand's deepest lake. Be warned! You are now in sandfly country and will need insect repellent. Also take note that that Fjordland, beautiful as it is, has the highest rainfall in New Zealand. Hence the term 'rainforest'. Keep a weather eye on forecasts.
Most cyclists continue on to Lake Manapouri, a quiet and beautiful lake with a small township that has campsites and a store/tea rooms and a few tourist amenities. The more curious among you may wish to take a cruise out to the Power Station on the far side of the lake and take the road (or catch the bus) to Deep Cove. From here you can catch the launch and explore one of the remotest fjords in the world. This is a tranquil, isolated and magnificent reach that stretches out toward the Tasman Sea through the great primeval forests of the Fjordland National Park.
A further flat 21k on from Lake Manapouri will see you in Te Anau, a recognizable tourist town with all amenities and plenty of hostels and campgrounds. The lake is pretty enough, but most cyclists regard Te Anau as the spot to consider the long road out to Milford Sound.