Melanesia is a region east of South-Eastern Asia, stretching into the Pacific Ocean. The people have brown skins and this is one of the characteristics that defines the people. Melanesia includes also the land of Timor-Leste.
Hitching will likely prove very easy, though one should beware of Raskols (Rascals, or armed local hooligans-bandits drunk on local alcohol in the highlands/mountains of Papua New Guinea), a continuous threat to the traveller, unlike the endemic tribal warfare. Ask around about the local situation, generally VERY SAFE, and the people in the remote regions ARE the friendliest people on this planet!
Generally you are supposed to offer to pay, much like you are supposed to offer to pay to camp, to pick food, even to walk across someone's fields, or through a village! In reality you may decide to pay for a local guide, or in the more remote places offer a couple of packs of noodles or other food, seeing as the local people may not have much use for money. If you just explain that you have no money, then likely you will be invited anyway to stay in the local village, journey on the local truck, or whatever, for free. But again gifts are very welcome, not necessarily money.
Even in Port Moresby international airport a quick enquiry determined the best guest house to stay, the same airport staff offered user jalanjalan a phone-call to book accommodation, a free lift to the guest house as they were returning home to the same area, and we went out and had dinner later that night!