Every morning there's a direct bus to the border settlement of Rusumo, from where you can take minibuses to f.e. Kigali. It will takes all day and you might need to stay overnight close to the border.
Since the buses depend on the ferries, they will leave at fixed times (usually 8am).
I missed the bus and the next one in the right direction finished in between at a relaxed place called Biharamulo, with has some very basic accommodation options. The next day I arrived around 3PM in Kigali.
I took a train from Dodoma to Mwanza and enjoyed it a lot! The scenery was beautiful, the cabins convenient and cold drinks and meals were cheaply sold.
Actually going straight to Mwanza from Dar/Dodoma v.v. railing is the only really comfortable option besides of flying, unless you're fond of 2 full days in a bus on dusty rough roads with 100 people inside ;-).
The journey took 26 hours, which included some hours of delay (it's only single track...).
Book 2nd (6 beds) or 1st class (2 beds)! Women and men are separated in 2nd class.
If you are going outside Mwanza, e.g. to Rubondo Island, Geita, Sengerema, Sunve or anywhere else you will undoubtedly have to take one of the big buses to get there. The Offroad Expresses. If possible, they are even more uncomfortable than the dalla-dallas. 150 people are stashed into buses that can only take 60, and the seats are worse and the trips longer than what you usually experience with a dalla. Add to that, the roads in the more rural areas are HORRIBLE and the drivers drive like mad med. It's actually not totally safe to go with these buses, and every week there is usually a bus accident or 2 on the way from Mwanza to Sengerema. But again, this is also an experience. You get on the bus by the Ferrey in Mwanza, pay 1-1500 for a seat and dump your belongings (keep your valuables with you). THen you leave the bus, struggle with 300 other people to pay for the ferrey and walk on to the ferrey. Here you go on the bus again and sit there until you reach your destination. If you don't get in your seat as soon as the bus gets on the ferrey, you can prepare yourself for a trip where you stand all the way. It's a battle and you have to use your elbows. Be prepared for a break down or 4 on the trip and be glad if you and your luggage get there without too many bruises. In the rainy season the off roads are pretty much the only buses who can get through to Mwanza from Sengerema.
From Mwanza you can go to Ukerewe with the M/S Nansio Ferrey which leaves by the fish market. This Ferrey is owned by a Danish guy and is the one ferrey on the Lake that is completely safe. It's probably also the only one that leaves on time, so if you miss this one, you either have to wait for the next day or take one of the 2 other ferreys that are not entirely safe. M/S Nansio departs from Mwanza every day at 2.30 pm and it takes around 3 1/2 hours to reach Nansio.
If you plan on going to Sengerema, Geita or Shinyanga you have to take the government ferrey from Mwanza that goes to Kamanga. It leaves every 2 hours. Don't take the ferrey after 4.30 - you can't be sure there are any cars on the other side, and if your car/bus breaks down you will be stuck int he middle of no where for the night, because no more cars are likely to come by. At the ferrey you have 3 or more options. Either you hire a taxi on the Mwanza side and ask him to take you the whole way, you get in an off road express and spent the entire time inside the bus, you go on board the ferrey and run as fast as you can to get a dalla on the other side (run! when they are full, they take off, and then you can risk being stuck in Kamanga until the next ferrey comes), you hitch a lift with a pick up truck on the Mwanza-side and pay him 1000 sh or you take a bicycle taxi when you reach kamanga. I always preferred just getting on the ferrey and running to the dallas. At the ferrey you stand in line (well, not really, but fight your way over to the man who sells tickets) and will be let on board when you have paid 300 sh. Then you make a run for it to get a seat. The trip lasts for about 30 minutes.
You have to learn to love it - the dalla-dalla's. This is the absolute most cheap means of transportation in Mwanza and actually also pretty easy to figure out and also reliable. A dalla-dalla is a minibus meant for only around 16 people, but usually closer to 30 people are squeezed in there. The dallas are run down and therefore break down ALL the time. If you are there for more than a month you are bound to experience this first hand. But there is always another dalla, so hamna shida! They don't drive very fast and because of the uncomfortable seats, the 2 chicken, a baby on your lap, the fat man sitting almost on top of you and the horrible, horrible roads, it cannot be called enjoyable. But then again, it's an experience and can be a lot of fun. You can't avoid getting in contact/conversation with the Tanzanians and really, when you think of it, it is quite hilarious. The dallas only drive when it is full (which means overcrowded) and you pay about 200 shillings to go from one end of the town to another. If you are not sure where you're going or where to get off, just ask the dalla drivers. They will know, and they will stop almost wherever you would like them to.
Mwanza actually has an airport. Or should we call it an airstrip? The easiest and most convenient way to get to Mwanza is by far with a plane. Planes leave daily from both Kilimanjaro and Dar es Salaam. Air Tanzania, Air Express and Precision Air all leave from Dar, while I think only Precision and Air Tanzania leave from KIA. The planes are perfectly fine, but don't expect them to leave on time. When you arrive in Mwanza you can either take the dalla-dalla or a taxi. It should not cost you more than 4000 tsh to get to town. When time is up for you to leave again, go to one of the travel agencies in town (Serengeti Services provides excellent service) or directly to the air companies. Precision Air has an office just beside New Mwanza Hotel.