Garang will be first vice-president in a Sudanese interim government agreed after two decades of conflict that has killed two million people and forced millions more to flee their homes.
Southerners can decide in six years whether to secede.
"He is a leader appointed by God and that is why we love him," said Mayom Ajok on Saturday, standing with thousands of supporters beside the airstrip at Rumbek, stronghold of Garang's Sudan People Liberation Movement/Army (SPLM).
"He fought for our rights and he brought us peace."
More than two decades of war in Sudan's oil-producing south was sparked by Khartoum's attempt to impose Sharia law on the rest of the country.
Garang flew in from a settlement further south where he had been consulting colleagues on how to implement the accord he signed with the Khartoum government on 9 January ending the country's 21-year-old north-south war.
Garang will be vice-president in
a new interim government
Garang later told a rally in Rumbek's Freedom Square that the SPLM's governing National Liberation Council would ratify the accord in the next 48 hours at a meeting in the town.
Sudan's parliament in Khartoum is also due to ratify the accord shortly.
As Garang emerged from the plane, six men held down a struggling white bull yards away and one slit its throat. Garang then stepped over the body in a ritual of honour and welcoming, and was greeted by his second in command Salva Kiir Mayardit.
Music poured from a brass band wearing red coats adorned with gold buttons and tassels and children waved posters that said: "We ask for the seed of peace to replace the seed of war."
Garang and Mayardit were presented with a live bull each. Garang named his Master of Peace.
The conflict between the government and southern rebels seeking greater autonomy has been complicated by oil, ethnicity, religion and ideology.
UN special envoy to Sudan Jan Pronk, who flew in shortly before Garang, said he would talk to Garang about the planned deployment of UN peacekeeping forces in the south.
The UN Security Council is expected next month to issue a mandate for a mission of military observers and protection forces. UN officials have said the mission will probably number between 9000 and 10,000 personnel in total.
"Religion has been one of the causes of the war. Bringing people susceptible to taking sides is not advisable"
SPLM official Pagan Amum
UN and SPLM sources have said the deployment of the mission may be delayed because of differences between the SPLM and Khartoum over which countries will contribute troops.
Pronk said he knew of no disagreements on the subject.
SPLA/M officials say they have expressed reservations about the countries who have volunteered staff for the UN mission.
One UN source said some nations including Egypt, Kenya, Pakistan, Bangladesh, Malaysia and India had offered troops for the mission. The source added that the SPLA/M were concerned about the predominance of Muslim nations on the list.
"This is an issue that's being discussed: how to get UN forces that are neutral, particularly countries that do not have material interests in Sudan," SPLM official Pagan Amum said.
"Malaysia has been on the side of the government in exploiting oil, and China will fall into the same category." On Pakistan, he said: "Religion has been one of the causes of the war. Bringing people susceptible to taking sides is not advisable."