Касательно самой Суматры почитать здесь и обратиться к thaiman-у за более свежими впечатлениями:
http://www.awd.ru/bb/viewtopic.php?t=11 ... 0%F2%F0%E0
Касательно транспорта:
Точно знаю из Медана и из Паданга можно морем добраться до Джакарты и обратно. Регулярное сообщение. НО! Это во-первых очень долго - больше суток, во-вторых тех. состояние и условия - мне лично не известны и непредсказуемы.
Есть вариант автобус+паром (и на Суматру, и с Суматры). Междугородные автобусы ходят по ТрансСуматрианской магистрали (одно название, далеко не везде есть асфальтовое покрытие) до порта на крайне восточной части Суматры, паромом до о. Ява и опять по суше до Джакарты. Бюджетно, быстрее чем первый вариант, меньше времени на пароходе - спокойнее. Автобусы вполне приличные.
На Суматру также можно попасть из Малайзии в Медан пароходом. Инфо точной нет. Слышал о нерегулярном сообщении.
Авиа - Летают по всем крупным городам Суматры. Насчёт международных рейсов - в Паданге точно они есть, в Медане здание аэропорта вообще вызвает сомнение, что там есть возможность где разместить паспортный контроль. Местные линии летают действительно все через Джакарту. Следует иметь в виду, что они иногда немного задерживаются и, если вы делаете стыковку, то надо закладывать дополнительные страховочные 1-2 часа.
Важно! В Джакарте все local рейсы летают с Domestic Terminal, a Garuda и ещё одна, точно не помню, летают доместик рейсы c International Terminal.
Авиасообщение между Меданом, Падангом и Джакартой авиакомпаниями Garuda, Lion, Merpati осуществляется на самолётах Boeing 737. Состояние хорошее, чистые, ухоженные самолётики. Еда норма. На маршрутах между указанными городами не трясло, не болтало, посадка вполне мягкая.
Вот Джакарта-Денпасар (Бали) - там трясёт, но это другая история...