Here is the official visa page for the Chinese embassy in Saigon. You can download a Word doc with English instructions; for the same information in HTML form visit the Chinese consulate in Vietnam's official site, last updated 2008. Here is the English version of visa application form (PDF, direct link).
In addition to the obvious forms, photos, money and passport, you'll need...
Documents showing the itinerary including air ticket booking record (round trip) and proof of a hotel reservation
You're going on a tourist (L) visa without an invitation letter, I assume. Get the airline ticket and cancel it after getting your visa. Do get a flight; it's possible for them to make a stink over having a boat or bus ticket instead and use that as an excuse to deny your application. Do the same with the hotel reservation, assuming you don't want to actually use it.
Proof of legal stay or residence status (applicable to those not applying for the visa in their country of citizenship)
If you are not applying for the visa in the country of your citizenship, you must provide the original and photocopy of your valid certificates or visa of stay, residence, employment or student status, or other valid certificates of legal staying provided by the relevant authorities of the country where you are currently staying.
You're an Australian applying inside Vietnam, so you'll need to provide proof you're there legally. They will need to physically see your Vietnamese visa and retain copies of it. It's prudent to also bring along copies of transit (flight, preferably) and accommodation receipts showing you've used mainstream methods to enter and stay in Vietnam. These would be a supplement to, not a replacement for, your visa.
If you have obtained Chinese visas before and want to apply for a Chinese visa with a renewed foreign passport that does not contain any Chinese visa, you should present the photocopy of the previous passport's data page and the photo page if it is separate, as well as the previous Chinese visa page.
They want to see your previous Chinese visa. But unfortunately, it sounds like you don't have it. This almost certainly rules out obtaining a longer term, multiple entry visa for you, since Aussies need to have a previous visa to obtain the multiple entry one. Also, a grumpy agent who reads this extremely strictly might say you can't get a visa there at all and need to apply within Australia; if that happens just apply again at a different embassy.
Is it up to me to provide evidence of my previous visits or do they just check my records?
It is most definitely up to you to provide this information. If you don't have it, the chance they will or can look it up is low. And even if they do see it in the computer, there is a significant chance that they'll discount it because you didn't properly submit a copy with your paperwork. Correct paperwork is correct obeisance to the Chinese government. You might get lucky, but I wouldn't expect this to work out in your favor. It bears remembering that "the consular officer will decide on whether or not to issue the visa and on its validity, duration of stay and number of entries in light of specific conditions of the applicant."
However, there shouldn't be any problems getting the typical "first time" (short term, single or double entry) visa without having a copy of your previous visa. If you're willing, you could roll the dice and tick "1 year / multiple entry" and hope the computer records do it for you; if not, the embassy will probably automatically downgrade you to whatever you are eligible for (though the price difference will not be refunded). There is some risk of rejection, but you could just apply again for the less useful visa if they're being sticklers.
The office hours, from the official website (translation by Google). You need to show up in the morning in order to be seen, and the office is closed on Chinese holidays. May Day is coming up soon; it's May 1 - 3.
Accepting applications for certificates, issuing time: Monday to Friday 08:30 - 11:00 ;
Chinese holidays (such as New Year's Day, Spring Festival, Qingming Festival, May Day, Dragon Boat Festival, Mid-Autumn Festival and National Day), the room is not external work visa. For other reasons, such as suspension of foreign work visas issued a circular room to advance.
The official Chinese embassies in Vietnam website (different from and more general than the Saigon embassy's site) lists the following fees and service times (translation by Google):
Third, the processing time: it normally takes four days. If urgent needs, rely on the relevant certificate to apply for expedited (first 3 days) or Express (the first two days, namely accepting 24 hours later) visa. Office Hours: Monday to Friday 8 : 30 to 11 time.
Fifth, the visa fee: a visa: 30 dollars; two Visas: 45 dollars; six months multiple entry visas: 60 dollars; one-year multiple visa: 90 dollars. Expedited fee: 20 dollars; Express Fee: 30 dollars. Note: Pay only accept US dollars.
Notice that last sentence: they only accept USD as payment! This page was last updated in 2008, so it may be out of date, though the office hours match the Saigon embassy's page. The Saigon embassy's page was last updated 2013, but unfortunately doesn't list fees or processing times. I recommend you call (not email) the embassy directly to get the latest information.
A matching listing of fees and processing times can also be found on chinese-embassy.info - a third party site, but it was last updated in 2009. Additionally, note that it specifies the fees are for Vietnamese citizens; foreigners may need to pay substantially more.
Visa fees (US Dollar)
Vietnamese Citizen
Single Entry: 30
Double Entry: 45
6-Month Multiple Entry: 60
12-Month Multiple Entry: 90
Express Service: 20 (2 working days)
Rush Service: 30 (1 working day)
Note: The normal processing time is 4 working days.
Office hours, from the same third party site:
Office Hours: 8:30-11:30 Monday-Friday
