It's the first visit by a Prime Minister to Australia's closest neighbour for five years.
Both governments see it as a chance to broaden the bilateral relationship from one that's largely been focused on aid.
Papua New Guinean women are also excited to see Australia's first female Prime Minister.
Presenter: Liam Fox, PNG Correspondent
Speaker: Ellenette Maamo, school principal; Jenny Hayward Jones, director, Melanesia Program, Lowy Institute for International Policy; Delilah Gore, PNG MP;
FOX: The Caritas Technical Secondary School in Port Moresby is bustling with activity. As the pupils at the all girl school go to class, workers are building a new library, four classrooms and a hostel that can sleep 114 students. It's all been made possible thanks to a two-point-two-million dollar grant from AusAid's incentive fund.
The principal Ellenette Maamo says it would have been years before the school could have built the facilities on its own.
MAAMO: We need them badly. For the hostel alone right now we are housing 40 students that should only be housing 30.
FOX: Education and infrastructure are two of the four priority areas of AusAID's development program here. This year the development program is worth nearly half a billion dollars.
For many years aid has been the focus of the bilateral relationship but when Julia Gillard arrives this afternoon the aim of her visit will be to recast it in broader terms.
HAYWARD-JONES: I think it's critical. We haven't seen a prime ministerial visit since Kevin Rudd when he visited early in 08 so massively important for the relationship to demonstrate that Australia is still keen to improve its relationship with Papua New Guinea and to set the relationship on a new footing.
FOX: Jenny Hayward-Jones is the director of the Melanesia program at the Lowy Institute for International Policy.
She says there needs to be greater official recognition of the growing economic links between the two countries.
HAYWARD-JONES: Papua New Guinea is one of Australia's top 20 trading partners, it's been steadily moving up the table there. We've seen much more investment - in fact I think Australian investment in Papua New Guinea is greater than Australian investment in China. That's an indication of how seriously Australian business regards opportunities in Papua New Guinea. So I think those aspects of the relationship are starting to overtake considerations about aid.
FOX: This trip is also shaping up to be important on another level. A visit by Australia's first female Prime Minister to a country where women are largely treated as second-class citizens will be a powerful symbol.
Delilah Gore is one of the three women in PNG's 111-seat Parliament. She's travelling from her electorate in Oro Province to be in Port Moresby for Julia Gillard's visit.
GORE: I met several women at the hospital and told them I'm rushing to Port Moresby because I'm meeting with the Prime Minister. And they were all so excited and they said pass our regards to the Prime Minister for Australia. Tell her we've been following her.
FOX: Ms Gore says Ms Gillard is an inspiration to Papua New Guinean women.
GORE: To have an Australian woman Prime Minister, it's really boosting us. In the future we want one Papua New Guinea woman to be a prime minister also.
FOX: As well as meeting her PNG counterpart Peter O'Neill, Ms Gillard is due to address the local Chamber of Commerce, visit the Bomana war cemetery and inspect a local market.