Thailand: visa-free for 30 days stay when arriving by air, but only 15 days at ground crossings. No restrictions on number of entries. If planning to stay longer, get a tourist visa at a Thai consulate (at home or in Vientiane, Laos). Tourist visas allow 60 days stay, extensible by 30 days.
Vietnam: visa-on-arrival available online (if arriving by air). You must get an authorization online a few days in advance. Many services available, I used cheapvietnamvisa.net and it worked ($8 visa + $45 stamping fee at the airport). For ground crossings, you must get the visa at an embassy.
Myanmar: visa required (from the embassy in Bangkok or your home country). If you only intend to go to border towns (e.g. Myawaddi, Tachilek) for a day, usually a visa is not required, you can just leave your passport at the border (and pay $10-$15).
Laos: 30-day visa-on-arrival available at most crossings, ~$40.
Cambodia: 30-day online e-visa ($25, quick processing) is convenient to avoid hassle/touts, but there's also the visa-on-arrival at border crossings ($20 official price, but they often try to charge more on various pretexts).
Singapore/Malaysia: visa-free for up to 30 days (I think, depends on nationality).
Info valid as of May 2013, watch out for changes.