A protest ban has been imposed in parts of the capital Delhi and throughout the states of Uttar Pradesh and Karnataka.
The new law offers citizenship to non-Muslim illegal immigrants from Pakistan, Bangladesh and Afghanistan.
Critics fear the law undermines India's secular constitution, and say faith should not be the basis of citizenship.
But Prime Minister Narendra Modi has dismissed their concerns, and said the opposition had been spreading lies.
There have been days of protests against the law. India's home minister has called a crisis meeting to discuss the demonstrations.
Tens of thousands of people took to the streets in cities across the country on Thursday, despite the police order based on a severely restrictive law which prohibits more than four people from gathering in a place.
Two people died in the city of Mangalore after officers opened fire on demonstrators allegedly trying to set fire to a police station.
Commissioner Dr PS Harsha told reporters that a curfew is in place in the city, and that he was waiting for a post mortem before announcing the cause of death for either man. Internet services have also been suspended in Mangalore for 48 hours.
Another man also died in the city of Lucknow, where violent clashes between demonstrators and police earlier in the day saw vehicles set alight. More than a dozen officers were injured and 112 people were reportedly detained in the city.
Civil society groups, political parties, students, activists and ordinary citizens put out a steady stream of messages on Instagram and Twitter, urging people to turn out and protest peacefully.
Among those who were briefly detained were Ramachandra Guha, a prominent historian and outspoken critic of the government, in the southern city of Bangalore; and political activist Yogendra Yadav in Delhi.
Speaking to the BBC's Newshour programme, Mr Guha said he had been arrested with hundreds of others from various different backgrounds, "which clearly shows that a large section of Indians are actually opposed to this discriminatory legislation".
Thousands gathered to demonstrate in Mumbai. Bollywood actors and filmmakers were expected to join the demonstration there.
What is the law about?
The law - known as the Citizenship Amendment Act (CAA) - offers amnesty to non-Muslim illegal immigrants from Pakistan, Bangladesh and Afghanistan.
The federal government says this is to protect religious minorities fleeing persecution in the three Muslim-majority countries.
But what has made the law especially controversial is that it comes in the wake of the government's plan to publish a nationwide register of citizens that it says will identify illegal immigrants - namely, anyone who doesn't have the documents to prove that their ancestors lived in India.
A National Register of Citizens (NRC) - published in the north-eastern state of Assam - saw 1.9 million people effectively made stateless.
The NRC and the Citizenship Amendment Act are closely linked as the latter will protect non-Muslims who are excluded from the register and face the threat of deportation or internment.
Why are people protesting against it?
Many Muslim citizens fear that they could be made stateless if they don't have the necessary documents; and critics also say the law is exclusionary and violates the secular principles enshrined in India's constitution.
But Prime Minister Narendra Modi said the law would have "no effect on citizens of India, including Hindus, Muslims, Sikhs, Jains, Christians and Buddhists".
He also blamed the opposition for the protests, accusing them of "spreading lies and rumours" and "instigating violence" and "creating an atmosphere of illusion and falsehood".