The bus terminal is west of the city center (it was moved there from To Chau on the other side of the bay around January 2008). There are buses from Ho Chi Minh City's Mien Tay terminal (about 8h) as well as from Can Tho and Chau Doc. The connection from Can Tho often requires a change in Rach Soi or Rach Gia from where it is about 1h.
The border near Ha Tien (7km to the north) was opened for tourists in 2007. It takes around 2h to go to Kampot by motorbike. As of April 2008, there were no buses connecting Ha Tien to Kampot. Some of the roads in Cambodia on the way to Kampot are not paved, but you will be able to see some nice rural areas there.
From Kampot you can get a motobike taxi for $9-10 or from Kep for $7 to the border on the Cambodian side. The road can vary in condition from paved and bumpy to packed dirt and bumpy, be prepared for a slightly white knuckled ride depending on the daring nature of your driver. Also, be aware that there seem to be Vietnamese drivers now waiting well inside the Cambodian side waiting to pickup (poach) prospective travelers to take them across the border into town. Your driver may stop here to talk with them and seem to suggest you go with them. A ride to town should be $3-4 or less (it is only 7 km and the road is well paved on the Vietnamese side.) If you can't agree on a price there you can simply have your Cambodian driver take you to the border where you can cross over and have the drivers on the other side fight over you.
The centre of town is easily walkable with Tran Hau the main commercial street running along the seaside between the big bridge for road traffic (Cau To Chau) and the former pontoon bridge for pedestrians (Cau Phao, removed in early 2007).
Try to get one of the tourist maps where the location of the temples are indicated.
There is no shortage of options for accommodation in this town. It seems that every other building is either a Kach San (hotel) or a Phong Tro (a place that has rooms to rent). The epicentre of sleeping options can be considered the area delimited by Tran Hau, Mach Thien Tich and Chi Lang streets.