Ho Chi Minh City to Shanghai overland
For most passports, the visas are easy to get in Singapore or Bangkok, but you need to allow several days processing time for each or pay extra for express service. If you plan on visiting Hong Kong or Macau, you will either need a multiple-entry Chinese visa, or you will need to reapply in Hong Kong or Macau, where Chinese visas can be obtained quite quickly for most passports.
See Discount airlines in Asia. Some of those have cheap flights between China and Southeast Asia which might fit in with this itinerary; as of 2006, there were no international LCC flights to Shanghai, but Air Asia has services from Bangkok to Xiamen and a whole host of carriers fly to Hong Kong/Macau.
Air Asia provide flights from Kuala Lumpur(LCCT), Malaysia to Hangzhou daily except Thursday. From LCCT to Guangzhou there is a daily flight, too.
The easiest but most expensive way to cross is the direct bus to Nanning from Kim Lien Hotel in Hanoi. There are also direct train services across the border.
The most popular route, though, goes like this. From Gia Lam station get on a bus to Dong Dang for around 60,000vnd. (You can also take a train, but the train station is further from the border.) They should drop you near the border and you'll only have to walk 200-300m to the Vietnamese passport control. The standard procedure requires you to throw your passport above the heads of the hoards of travelers through the hole in the office window and wait until you notice an official wandering about with your passport. Good luck.
Once you're stamped you can walk the short distance into China and enter the marble tiled efficiency of Chinese immigration control. When they set you free you need to get to Pingxiang 15km away. Don't accept the first taxi tout but wander around through the huge stone gate, see the motobike taxis and get a bidding war started. A taxi should only cost around ¥30 and a motorbike no more than ¥20. From Pingxiang get the bus to Nanning. They are more regular than the trains and this will take about 2 1/2 hours. You will arrive at Lang Dong station.
From Nanning you need to travel over night to Guangzhou. If you are happy with a sleeper bus, Langdong station is the right place to be. Bear in mind the journey by bus will take 10 to 11 hours and cost about ¥230. If you want to catch a train, which may be cheaper depending on your level of endurance, get on the number 6 bus (¥2) to the train station (huoche zhan) which takes about 20 to 30 mins. This is the better option because even if you can't get a train you can buy a bus ticket at the Lang Dong station ticket office on Chaoyang lu near the Yin He hotel, which is a two minute walk from the train station. This way you can see some more of Nanning before catching the No 6 back to the bus station. (Allow 50 mins). When in Guangzhou get yourself to Guangzhou east station and use the new metro for about ¥5. Once there follow the signs for the Kowloon express and for ¥180 you'll be in Hong Kong in less than 1 1/2 hours. You will arrive at Hung Hom station and it's just one stop on the MTR to get to Tsim Sha Tsui east where you can find all the budget accommodation in one of the two "mansions" on Nathan Rd.
If you want to skip Guangzhou/HK, direct train services are available from Nanning to Shanghai. Many would probably visit Guilin, which is a few hours from Nanning along the rail line towards Shanghai. Before Shanghai, the city Hangzhou is probably worth a visit.
Alternate route through Kunming
If you have the time and money, you could swing further west into China.
It is quite easy to take a train from Hanoi to Lao Cai at the border and cross the border to Hekou, Yunnan before taking a bus to Kunming, where direct train services are available to Shanghai. The rail service from Hekou to Kunming is currently under maintenance.