I think I will try and reply in reverse order so my post makes some sort of logical sense. [Edit: Its all over the shop, due to more posts while I was at work]
The various aboriginal people's of Australia, making up many nations, languages and cultures have been here for at least 50,000 years. It is the oldest continuous civilisation on Earth. I was arrested in 2002 repeatedly (but never charged) defending a 7,000 year old burial site of a Kuradji (sort of like a Holy man) who was still talked about in local dream-time stories. That is continuous culture that is as about as old as writing itself. The British didn't invade until 1788. 50,000 years to 229 years, I think they have a pretty good claim to be called indigenous.
There are a few main reasons a Treaty is preferable to Constitutional recognition, firstly it recognises indigenous sovereignty pre-dating invasion. Secondly, it is not another case of the invaders doing something without the consent of the original inhabitants. Thirdly you sign Treaties when you end wars. I will deal with each in turn.
When Britain first invaded Australia, the land was declared Terra Nulius, or uninhabited land because it, according to British definitions had never been subjected to soverignty by any state. This was overturned by the Mabo ruling in 1992, when the High Court declared Terra Nulius a fiction. The British argument was that aborigines didn't cultivate the land and therefore it wasn't theirs. However, between land management practices, most notably fire-stick farming, areas which farmed fish and yams, there was agriculture, it just wasn't recognisable to the colonists. A brief article covers examples of land management here.
The Mabo ruling recognised for the first time that indigenous sovereignty pre-dated invasion. This is an important change in the relationship between the colonisers and the aboriginal peoples.
By undoing Terra Nulius, land rights were recognised for the first time. Yet it is another case of the colonists deciding for the aborigines, just like the 1967 referendum and the Wave Hill land grant by the Whitlam government.
Rather than just continuing the practice of deciding for and on behalf of indigenous Australians, a negotiation for a Treaty would recognise aborigines as equals in the project of Australia.
Ending the War
Colonisation is a brutal process. By the time Australia was colonised, the British had this down to a fine art and had built up the ideological mind-set where they believed they were bringing civilisation to the darkest corners of the globe. From the time of Lachlan Macquarie onwards there was a genocidal campaign against the indigenous population.
Many aborigines alive today have been taken from their families, continuing the cultural genocide long after the last official shots were fired. The last of the official "Stolen Generations" are about my age, and I have a friend who was taken from his parents and raised by a foster carer. This seems to be ongoing too, with reports of a higher rate of family separation today than during the years of the Stolen Generations (the stats are linked in the article).
Incarceration rates are shocking, with some states having rates worse than anywhere else in the democratic world. Life expectancy is dramatically shorter too. The war needs to stop. When you end wars, you sign Treaties.
Every other country colonised by Britain, where Europeans came to dominate demographically has signed Treaties with the indigenous populations, no-where have they managed to wrest an inordinate amount of power from the colonisers.
What they request is not up to us, it will be up to the indigenous body to determine. What gets decided in the negotiations will be up to the government of the day, not us as a Party (unless we are somehow the government). Personally I would be happy with some seats in the Senate or similar, but again it isn't for us to determine.
The convention in Uluru put together a working group to determine how a representative body would be formed. We will hear about it in the next six months to a year I suppose. As long as its democratic and doesn't disadvantage any groups within the indigenous population, it will be fine IMO.
I don't think they would want to add a layer to the government. It is hard to know exactly how it would work because this is the beginning of the process and there are too many questions that have yet to be decided, and it is not up to us to decide their negotiating positions.
To be clear, the idea for our policy is to help facilitate an act of self-determination by the indigenous population of Australia. The details will come after they go and determine what they want.