There are several night trains each day from and to Hanoi (about 9h, ca. 20$ for a soft sleeper depending on the train).
Buses run from Kunming and other cities in Yunnan (China) to Hekou from where it is a short walk over the border to Lao Cai. The border is open from 7am to 10pm (8am to 11pm Chinese time). Crossing the border is pretty easy and fast. Just be careful on the Vietnamese side of the border. you might be asked to fill in a 'health form', exchange money, book a taxi, etc... by people who seems to be immigration workers. These are all scams, you will lose money if you agree. Don't give them any bribes and don't use their services. Just ignore them, get your entry stamp and leave the immigration building. There is a 2 km walk to the bus/train station, 30000 dong by car taxi.
Trains run from Hanoi to Lao Cai. One train starts at about 6 am and arrives at about 6 pm. There's a simple restaurant on the train. People sell food through the windows or walk through the train during stops around lunchtime. There are 220 Volt / 50 Hz power outlets in the soft seat coaches.
The price for soft seats of the Hanoi - Lao Cai train is VND 155,000, and the Lao Cai - Hanoi train is VND 150,000. Tourists can buy Sapa train tickets directly at Hanoi railway station gate on Tran Quy Cap street. You can also buy at the website of the Vietnam Railways or other booking websites.
The best place is known as Sapa ( can cau, bac ha. Sima Cai, coc ly local markets). However, to get to the local market is quite hard for travelers due to the traffic. Travelling by train from Hanoi, then getting a car might be your best solution.
There are a couple of ATMs in Lao Cai. The Techcom Bank has ATMs on the square of the train station as well as close to the border. However, they accept only some international cards. There is one ATM accepting all international cards but it's neither close to the border nor to the railway station. Motorbike drivers usually know it and will drive you there (one-way 10'000d)
As soon as you leave the immigration building you will be approached by money changers. They usually offer poorer exchange rates than the bank. There are two banks just next to the border and a third one just at the other end of the first bridge, though these are all annoyingly closed at weekends. Banks in Hanoi will also readily exchange your RMB for Dongs.
There are plenty of hotels that are about 10 minutes from the border in the Coc Leu area, just over the last bridge before you enter the Vietnamese immigration area. It's not a bad place to spend the night. I paid 170000 dong for my double room near the first roundabout, opposite Agribank. There is a night market opposite the lake about 3km south, and the walk along the river overlooking china by the footpath is also pretty quiet.
You can get free wifi near bus/train station at the Fansipang restaurant and Le Bordeaux restaurant, both are visible from station.
When you exit the train station at Lao Cai, there will be a row of small coffee stalls to your left. The one nearest to the main station entrance is run by a seemingly (and overly) friendly middle–aged woman who will try very hard to get you to her stall to have some coffee. She will tell you when the next bus is going and then tell you to come wait at her stall. Do not go with her. She will sell you small coffees (that should absolutely cost no more than 20,000 VND at a stretch) for 50,000 VND each. That is how much a Starbucks cold brew costs, and for that, you're not getting a lukewarm cup of coffee that you drink sitting by the roadside inhaling motorcycle/bus/car fumes.
Recently a guy will be approaching you, yelling your destination and leading you to rows of buses. He will pretend to be a driver, do not trust him. He will help you into the correct bus and demand payment. If you disagree, he will try to negotiate for a lower price. This person has nothing to do with the bus company and the real drivers will not get involved and stop him.
Lao Cai does have both, public bus, and train station - together they constitute the center of town. While the train station can be found right next to the main road, the bus station is situated around 300m south-west of it, down Phan Đình Phùng. Additionally, mini buses are abundant (destinations usually indicated behind wind shield), which will drive around town until full and can be flagged down - prices are fixed but conductors usually try their luck and ask for more, including mock tickets with fake prices.
Trains run from the train station in Lao Cai to Hanoi - with the option of an overnight sleeper. This will however put you in Hanoi rather early with the only company being a million motorcycle and taxi touts. So its generally a good idea to have a plan as to where you will be heading to on arrival to avoid being scammed. Prices for a soft sleeper ticket are around 300,000 dong, lower classes are cheaper. Check http://www.seat61.com/Vietnam.htm for up to date information on prices.
Train Company - Livitrans
There is also a bus service to Hanoi costing 89'000 dong.
Night bus to Hanoi. Costs about 150000 dongs. Very uncomfortable with loud music and no leg space. Train is much better option, but often need to be booked in advance.
Minibuses run from outside the chinese Hekou border immigration exit, and train station straight up the mountain. Cost should be 50,000d per person and the bus leaves only when it is full.
As of August 2014 there is a public bus service from Lao Cai to Sapa for 28,000d per person, leaving from the train station at 7:30, 8:30, 9:30, 10:30, 11:30, 12:30, 13:30, 14:30, 15:00, 15:30, 17:30. The station is clearly marked "buses to Sapa" in the train station parking lot, and the buses are white, yellow and red. If you're carrying a large bag you might be asked for an additional 15,000d. Note that this is an extremely bumpy ride, and many passengers tend to get sick - the staff offers plastic bags, water and moist towelettes to the passengers.
If arriving via the chinese Hekou border, watch out for touts who will persistently attempt to get you to pay anything up to 150'000d, or ¥20 (approx 50'000d) per person to get to Sapa. Just ignore them and walk to a main street and flag a minibus with a sign showing Sa Pa at the windscreen. Confirm with the driver or bus attendant 50'000d and hop into the minibus to Sapa.
If arriving by train (usually at around 5am - 6am) watch out for minibus scams asking for 200,000 dong upwards. Generally they can still be bargained down (despite much disgust from whoever is so kindly scamming you).
Bac Ha, with it's Sunday market, can be reached via public bus from the Lao Cai Bus station in around 2.5 - 3 hours for 60, 000 dong
About 40min walk from bus/train station, is the border crossing to Hekou in China. Border office is a big building next to a bridge, opposite Sapaly hotel / Biti's trade center. From here you can catch an onward connections to Kunming as well as other locations in Yunnan/China (see Hekou#Get out for up-to-date information).