From Ho Chi Minh City there are several companies that operate bus services to Rach Gia. The one with usually the best busses is Phuong Trang  (website in Vietnamese only and had no actual departure times). They depart from the Mien Tay bus station at bus station 395 Kinh Duong Vuong, An Lac Ward, Binh Tan District. You can get there by bus 2 from Bin Tanh Market (5,000 VND) but this service stops at 6 PM. After that time you can take a taxi to go there. From the backpacker district this will take about 40 minutes and should cost around 140,000 VND. Another option is to go to the Phuong Trang office at 328 a le hong phong street, district 10 to buy your ticket there. They have a free bus service to the Mien Tay bus station from there. This office is only a 10 minute taxi ride away from the backpacker district and should cost around 60,000 VND. The bus ride from Ho Chi Minh City to Rach Gia should take about 6 hours. You can also go for the night bus (165,000 VND). Best option for that when traveling onwards to Phu Quoc is to catch the 11.45 PM nightbus. It has two rows of bunk beds. Seat numbers starting with A are below, B are on top. Avoid getting a bed assigned above 15 as these places are actually one big bed with 5 people sleeping cramped up next to each other. This nightbus will arrive in Rach Gia around 5 AM where you will have to change to a smaller bus. This will take you all the way to the harbor from where the boat departs where you will arrive around 5.45 AM. You will then have to wait about 2 hours for the first boat at 8 AM to Phu Quoc to depart. There is a paid toilet (2,000 VND, no toilet paper) and several stalls where you can get some food. There are stories that other bus companies than Phuong Trang do not take you all the way to the harbor but to a smaller bus station in Rach Gia instead. From there you can negotiate with a motorbike driver to take you to the harbor for 30,000 to 60,000 VND. Make sure you book your bus ticket in advance (day in advance in possible). Call the bus company to reserve seats or stop by their office as these busses tend to be full.
From the Cambodian border, motos can be hired to Ha Tien, from where buses connect to Rach Gia. The green mini-buses of Mai Linh company are faster as they do not stop to collect passengers along the way. If these are full, the marginally-cheaper local bus also plies the route. It is best to wait for the bus in one of the cafes on the road leading out of the bus station, since the bus will crawl out of the bus station at the scheduled departure time, but take 10-15 minutes to reach the main road as it tries to drum up more passengers.
There are only hydrofoils left to Phu Quoc. Other ferry services have stopped their services. Hydrofoils to Phu Quoc leave at 08.00, 09.00, 12.40 and 13.00. Actual departure times and prices can be found at the website of the boat operator SuperDong . A ticket on the boat costs 320,000 VND. The journey takes 2 1/2 hours. There are lots of ticket offices near the port where you can buy a ticket.
As of December 2013 there is an 8:00 AM and a 1:00 PM ferry that takes about 2 1/2 hours and costs about 160,000 VND.
There are motorbike taxis which will take you from hotel to bus station etc.
Phuong Trang bus company (phone 0.77 3.691.691) connects Rach Gia to Can Tho (~every hour between 3am and 6pm, 80,000 Dong, ~3h) and Saigon (9 a day between 7.30am and 12am, 120,000 Dong). Several bus companies make the journey with the option of a seated or sleeper bus.