Ok, I've done 4 budget trips in the area.
1st trip, (2months) LA - NZ, Australia, Bali - Australia-LA
2nd Trip: (2months) Bali-thailand-Laos-Bali
3rd Trip: 7months) Singapore-So India, No India, Nepal, BKK, Chang Mai - Laos (all the way through Laos) - Cambodia - Bali
4th Trip: (7weeks) Singapore - Malaysia Borneo - Bali - Sulewesi - Singapore
Another to come shortly!
I usually travel on $10-$15 per day. (it's pretty basic - but pretty clean & safe)
Tips: Don't book anything ahead of time! Except dive reservations in Malaysia Borneo & Julies guest house in Chang Mai.
Visit the "Lonley Planet - Thorntree fourm" for much better budget travel info
Thorn Tree Travel Forum - Lonely Planet
Here some of my favorite highlights - you can link them.
Chang Mai Thailand is a great place to get orientated Check out Julie's Guest House- Skip trekking here it's impacted. For some relaxing fun- head west to the little mountain town of Pai where you can guide your own hikes & explore the countryside if you rent a motorscooters. It's cheap. I stayed at a little hippy dive on the river called Golden Huts for $7 a night.
You can catch a bus directly to Chang Kong & the Laos Border (get a visa there) - BUT DON'T GO SOUTH TOWARDS LUANGPRABANG with all the other tourists. The north has the most colorful culture!!!! Don't miss out!!
Take a boat or bus up to Luang Nam Tha - from here you can get to some of the best ethnic jungle trekking. For easier access & more amenities head N to Muang Sing (everything can be organized there) - for more remote and creative adventure head through Udomaxai to Phongasali (trekking agency here) Very cool stuff & probably little to no tourists. If you make it to Phongasali - then you can travel 2-3 days down the river towards Luang Prabang & meet "civilization" again where you'll probably spend 4-7 days dusting off.
In the south of Laos I've heard Savannakeht is nice, Vang Vien is a party spot but the 4000 islands on the southern border are a nicer chill/party spot - there is one island with a remote home stay think it was called Don Kho - you will find info in the gvt travelers info shop in Pakse - if you make it that far down. I can recomend Kiet Ngong (near Pakse) if you want an authentic traditional village homestay. Try to arrange a full day elephant jungle trip - it should run $20 for 2 people ;-)!
Now you have a problem - the amazing rock climbing is in the south of Thailand near Krabi and you have to go to Anchor Wat in Cambodia!
Work it out
! Airasia.com should help. But best to get to Rai Leh beach before late October as it gets very busy over christmas! Also it's less expensive to stay in bunaglows in Hat Ton Sai! If you like sport climbing - you'll over this place! It's very hard to leave & there's plenty to do for your non-climbing partner.
To keep Anchor Wat inexpensive, find a guest house for $6-$7 per night, Pay for a 3-5 day pass, find a self-guide book - Maybe $20 per day OUCH! and rent a bicycle & do the tour yourself (18+ mile ride feels great!)
Ok so now that you've treked through remote jungles, lived with about 3 different tribes of indiginous people, floated on rivers for days, probably explored a cave or two, done tons of shopping, soaked in the hotsprings in Pai, had an elephant safari, checked out one of the biggest ruins in the world, probably ate a few insects, wandered amazing temples of Luang Prabang, indulged in Thai food and spent a few weeks in the south of Thailand cranking it up limestone cliffs & enjoying the amazing scenery - time to get busy diving if you haven't already!
So do not miss Malaysia Borno - Semporna (bring your own reg) and dive with scuba junkies (homestay on Mabul is $18 per night - 12 person dorm room hell is $3)
http://www.scubaboard.com/forums/malaysia-singapore/270713-whats-word-scuba-junkies.html#post4199553 I started researching traveling down through Indonesian Borneo and taking a boat to Sulewesi - then traveling overland to Manado (I didn't do it, but it looks cool)
In Manado - dive your heart out at Bunakan/Lembeh
Bunakan - Stay at Lorenzo II on Bunakan for about $18 including food - book ahead & dive where you like - lots of shops and prices are good. In Lembeh Straights (a do not miss) there are a few on land inexpensive resorts - check LP or PM me if you want details.
Also hit Bali, here are details -
http://www.scubaboard.com/forums/ge.../272244-inexpensive-diving-2.html#post4220941
I've heard lombogen is amazing (I'll probably head there this summer) & also to the philipines (looking forward to detailed info for both on this post) - also hope to travel into Burma one of these days soon ;-).
Another really cool option is to fly into Singapore & take a shuttle to the south of India for a month. I caught a $120 flight on air india express! Once you are in india - book inexpensive flights on Yatra.com.
I heard there are inexpensive flights from Bali to Australia? Maybe try jetstar? It's only a few hour flight.
Of course you could reverse this entire plan to take advantage of weather but there will be more tourists. Have tons of fun!
K
Ps: Keep in mind that airasia.com is a great resource. Book online with your credit card and use the flights as shuttle buses all around SE Asia. Very inexpensive!