Mr Abbott says Australia looks forward to working closely with the new Indonesian leader.
He adds that the the election is a significant milestone, describing it as part of a "remarkable transition" to democracy.
Prime Minister Abbott says Australia's relationship with Indonesia is extraordinarily important.
Mr Abbott has also paid tribute to outgoing President Susilo Bambang Yudhoyono, saying he has provided Indonesia with wise leadership and political stability.
In response to the new Indonesian presidency, Washington says its relationship with Jakarta had strengthened to the point where both countries can jointly address regional and global challenges.
The U.S. Secretary of State John Kerry says Washington looks forward to working with President-elect Widodo, and to expand people-to-people ties with Indonesia.
Presenter: Sen Lam
Speaker: Bates Gill, Chief Executive Officer of the United States Studies Centre
GILL: Obviously, Washington is pleased that this has not been dragged out into some sort of court battle and pleased that the results can be largely seen as having come at the end of a democratic process in this critically important country. So that's all good I think that's the right tone going forward.
Secondly, there's great expectations I think for Indonesia to transform itself into the kind of economic power that it surely has the potential to be. I would think the Obama administration would want to see the new leader open the doors a little bit more to foreign investment, reform its economy at home, put in place the kinds of infrastructure and other improvements that can help the Indonesian people reach their full potential.
LAM: Do you think the United States is also eyeing Indonesia as an increasingly important partner in Asia, against this backdrop of a China that's growing in power and assertiveness?
GILL: Well, the United States and Indonesia have had an on again, off again kind of relationship.
Indonesia, a proud nation, still I think tries to position itself as something of a neutral player in the international system. It's always going to be wary of linking itself to closely with one major power or another. That said, the past several years have seen a sort of rebirth, I guess you could say, or a nascent security relationship beginning to build between the United States and Indonesia. And I think the United States would probably like to see that strengthen down the road.
It's not necessarily a play to sort of counter balance China, but, I think, given the enormity of Indonesia, its potential as a leader in Southeast Asia, its geographic positions, straddling such vital sea lanes of communication, the United States does have a larger interest I think in assuring that Indonesia can make a positive contribution in security in the region. And so I think we should expect a closer relationship between the two countries going forward.
LAM: And, given the geographical proximity of Australia to Indonesia, and Australia being a very close partner with the United States, what role do you think Australia, or indeed, the Obama administration might expect Australia to play here?
GILL: Well, of course, being closely allied with Australia, we have a lot of shared interests in this part of the world, I think we should expect to see Australia playing a bigger role. I think Washington would certainly welcome that. And most of all, in engaging with countries in Southeast Asia, and, of course, the South Pacific, where Australia plays such an important role as security actor.
Now, I think Washington probably needs to come to understand a little more clearly, the long history of relations between Australia and Indonesia, recognise that there still remain a number of major difficulties and sensitivities in that relationship, and so therefore not have overly high expectations about what Australia might be able to achieve.
But I think any improvement in Australia-Indonesian relations that can be developed over the coming years would surely be welcomed in Washington.
LAM: Is Joko Widodo the more comfortable option for Washington? It's been suggested that the more controversial Prabowo might have been a most awkward proposition for the White House had he won. What do you make of that?
GILL: Well, I think there might be something to that. At the end of the day, obviously, the most important thing I think for Washington is that the Indonesian people come to a decision that's peaceably decided and democratically selected. So I think that's the most important thing, but yes, I think given the past record of Probowo, it might have been a little bit awkward for President Obama, but I think we still don't know all that much about the new leader and so I think we're just going to watch carefully and hope that we can develop a good relationship.
LAM: The downing of the Malaysian airlines plane last week is currently dominating news, of course, eclipsing tensions in East Asia, between China and its neighbours. What do you make of the description of China being 'the new Japan', meaning that the 20th century regional distrust of Japan has now shifted to China?
GILL: I think it's a little bit to early to equate China today or maybe even in the future, with the role that Imperial Japan played in the early part of the 20th century, leading to the Pacific war. Yes, China is seeming to be flexing its muscles a little bit more.
I don't see China as having sort of the grand territorial ambitions, a greater East Asia co-prosperity sphere as it was called during the period of Imperial Japan, but it is troubling. It strikes me as at odds, with what ought to be China's longer term interest, which would be to assure it has a constructive set of relationships with all of its important neighbours, not least the United States and Japan. And it seems under the currently leadership China's taking some steps to undermine that overall strategy.
But in response, we're going to see more of what we're seeing now, and that is an increased interest in an American presence in the region by most of China's neighbours - a sort of tightening of security relationships between the United States and its allies and other friends and partners in the region, and a kind of continued uptake in tensions between the US and China.
LAM: So given that background, do you think the US would be, if not comfortable, perhaps even pleased with Japan's somewhat more muscular military posture now, vis-a-vis the re-interpretation of its pacifist Constitution?
GILL: Well for many, many years, and well prior to the current tensions that have arisen between China and Japan, Washington has sought to encourage Japan to have a more constructive role as a security actor in this part of the world.
Washington knew that that is sensitive and may well require some reinterpretation of Japan's post-war Constitution.
The important thing for the United States is that Japan play a more a positive security role, contribute more actively to assuring security in the region, but do this in a sensitive way. Recall that Washington was not happy with Prime Minister's Abe's visit to the Yasakuni Shrine back in December. There was disappointment on the US side that he would take such action.
So it's a tricky balancing act, while Washington surely would like to see Japan play a more active role, commensurate with its economy and importance in the region, it has to be done so in a very, very sensitive way, in a way that does not led to increased tensions or more conflict.