Thailand: visa-free for 30 days stay when arriving by air, but only 15 days at ground crossings for most nationalities (as of Oct 2013, 30 days at ground crossings for G7 countries: USA, Japan, France, Germany, Italy, UK and Canada). 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 single-entry visa-on-arrival available at most crossings, ~$40.
Cambodia: 30-day online e-visa ($28, 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 updated in Feb 2014... do watch out for changes.