The three primary transit points are all close to each other and you should be able to get a motorbike taxi between them for 20-30,000 dong or thereabouts.
Baichay Bus Station. The primary local bus station. Connects with destinations right across Vietnam, as well as Vientiane in Laos and possibly Nanning in China.edit
Tourist Ferry Pier. The huge array of slow 'junk' tour boats for package tourists out of Hanoi depart here for Cat Ba Island. As most people taking these boats are on pre-booked tours, the piers are not exactly set up for independent travel. In fact, quite the opposite; you will be approached by hawkers wanting to make a quick buck by selling you tickets for a premium: avoid these guys. What you want to do is get yourself a ticket from the row of counters inside of a building near the waterfront. Tickets are 80,000 dong for 'route 1' which is the standard way to get over the Cat Ba. Wait around there with the locals (the group easy to identify as "not lost looking western tourists") until something happens. For individual tourists not on a tour package from Hanoi, "licensed" agents will approach you upon arrival at Bai Chay Wharf to sell cruise packages to you. Starting prices (for a non-Vietnamese Asian) are 500,000VND for a 4hr cruise (for which you will receive an 80,000VND cruise ticket) and 800,000VND for a 6hr one. If you want to avoid the hassle of buying tickets yourself and not looking like a lost sheep not knowing which cruise to take, do your best to bargain. You could approach the ticket counter directly if you have a Vietnamese-speaking guide along, and the rates will be much lower (remember, it's an 80,000VND ticket), but be prepared to pay higher than the value stated on your ticket due to other surcharges such as mandatory insurance. The tourist boats just stop at an island with two poorly preserved caves, and passengers are hit up for overpriced beers and kayaking ("the water cave") along the way; the whole ordeal takes four or five hours and is really best avoided unless you've never seen a cave before or want to hang out with clueless gap-year tourists. You can talk with the quide, who takes a tourist group on the pier, buying cruise or transfer to Cat Ba with him directly. If they have empty rooms on the boat, they will happy to take you. 2 day 1 night all inclusive cruise is less than 40 USD. An old report claims "There is another government-run ferry leaving the tourist wharf at 12:00 daily costing 100,000 VND per person and takes 5 hours. This arrives into Cat Ba town" (Good luck finding it with no further information...)(20.946862,107.030159)edit
Đảo Tuần Châu Pier. Fast ferries depart from this pier on mainland-linked Tuan Chau Island 3 times daily: 9:30, 11:30 and 15:30. (50,000VND; just over an hour). Nice scenic route but then all routes to Cat Ba are. Cars and bikes also take this route. Be warned though, especially during off-peak season, that the ferry will only leave if there are more than 20 people using it. It also arrives into a lesser used port on the northern edge of the island, about 25km from Cat Ba town. A local bus can be taken to town, costing about 10,000VND per person, or an array of motorbike taxis await. Be wary as enterprising local businessman may try to convince you the local bus is his personal taxi, and charge you extortionate rate to use it.(20.934867,106.998382)edit
There are many restaurants opposite the beach offering mostly Vietnamese rice dishes and seafood. Local specialities include su fish, found only around Halong Bay, shrimp and mussels.
Emeraude Café, tel. 033 849 266, on the Bai Chay coast near the post office. The only restaurant in the area that serves Western food.
Co Ngu Restaurant -  tel. (+84 33) 3511 363, Premium Villas, Halong road, Bai Chay, Halong city, Quang Ninh. A wide selection of Western cuisine and Asian delicacies is served at this premier local seafood restaurant.
If you are unable to find a hotel within thirty seconds of arrival in Ha Long city, then you may have been dropped off in the wrong place. There are plenty of Nha Ngi and Hotels lining the streets vying for your money, so haggle it up.
Halong Backpackers Hostel (Viet Anh Hotel) is right on the entrance to Anh Dan street, and is easy enough to find and close to the beach. They do not appear to have dorms. Wifi. Twin rooms start from $15 / 300,000 dong.
Tuan Chau Island Holiday Villa is located on Tuan Chau island, and boasts a private sand beach and a themed park. The resort played host to Miss Universe beauty pageant in June 2008. Cab ride to Bai Chay Tourist Wharf is approximately 10mins and 150,000VND (7/8USD). From 80USD per night.
Apparently there are some old stone houses in the mining town of Cam Pha, which you can reach by local bus from Baichay Bus Station. Your mission, should you choose to accept it, is to find them, take photos, and update this page. To aid you in your mission there is a French 1915 map of the mines of the area over here, featuring an ancient citadel.
Also note that if you travel east that far, you would do well to push on to Cai Rong and take a slow ferry to Quan Lan Island, totally free from tourist hassles.