South towards Lusaka
If you're heading back south through Zambia, head along the main road through town over to the harbour compound. Mpulungu is Zambia's only port, and is on Lake Tanganyika. Trucks queue outside the compound waiting to off-load or load their freight in the harbour and often leave town the same day. You can ask the drivers here about their destinations. If there are no trucks around you can walk a little way into town and try for any vehicle headed south. If you want a truck (given they generally travel longer distances), another option is to enter the harbour compound and politely ask the security staff to check their log-books for departing trucks that may still be in the compound, somewhere out of sight. I thought this best and tried it, and it worked. There is also a little bench nearby where you can sit and wait for the truck. Again, be patient, it pays. As this is a good place for information, remember to be polite and respectful to the harbour staff, because it's right and also so that they will continue to be helpful to other travellers.
The M.V. Liemba is a ferry that travels up and down Lake Tanganyika between Mpulungu and Kigoma, Tanzania. From Kigoma you can easily continue over-land on to other points, like north to Burundi which is not far away. Ask the harbour staff for details on the Liemba's schedule, as it often changes without much notice. It will take some skill to hitch a ride on the ferry, and if you do, be prepared to sleep on the roof or near the steam stacks, under the stars.
South east over-land towards Tanzania
Hitch from the same point outside the harbour at Mpulungu and take trucks going to Nakonde, on the Zambia-Tanzania border. If you get stuck in this town (Nakonde), which is unlikely, as there are many trucks at the border post, you can always catch the Tazara train which goes all the way to Dar Es Salaam.
Places to avoid
Don't walk to far out of town before you start hitchhiking. On exiting Mpulungu when headed south, the road follows a steep, winding course through the hills, and the truckers are less likely to stop for you once they've picked up momentum.
Accommodation and Sleep
Various budget accommodation options in town and along the lake.
Other useful info