Take one of the many regular buses to the new Trat bus station from either the Eastern Bus Terminal (Ekamai) or the Northern Bus Terminal (Moh Chit). Daytime direct 1st class buses from Ekamai(~240B) average a bit more than 5 hours, while the less frequent services from Moh Chit take a little less; late-night services are quicker still. While most 2nd class buses(188B, air-con) take a bit longer as they may make more stops and use slower and less direct routes. The midnight departure from Ekamai takes only 4.5 hours.
From Trat bus station, take a minibus direct to the Hat Lek border crossing - departures every 45 minutes between 06:00 and 18:00, takes between 1.5 and 2 hours, 120 baht.
Cross the border to Koh Kong. The border opens at 07:00 and closes at 20:00. If you want to go on directly to Sihanoukville by sea, keep in mind that the boat is scheduled to leave at 08:00 (in practice it often leaves a little late - typically around 08:20).