How did it work?
When Lucius Fox and Bruce Wayne are discussing the device (around 33 minutes in), we learn that the device really is powered by sonar:
[Lucius hands Bruce a phone]
Bruce: What’s this?
Lucius: I had R&D work it up. It sends out a high-frequency pulse; records the response time. For mapping an environment.
Bruce: Sonar. Just like a…
Lucius: Submarine. [nodding]
We get confirmation that it’s sonar at the 1 hr 56 min, when Batman shows Fox his mass-scale implementation of the idea. As far as I know, this is also the closest we get to knowing whether it’s software or hardware.
Batman: Beautiful, isn’t it.
Lucius: Beautiful? Unethical. Dangerous. You've turned every cellphone in Gotham into a microphone.
Batman: And a high frequency generator-receiver.
Lucius: You took my sonar concept and applied it to every phone in the city. With half the city feeding you sonar, you could image all of Gotham.
Unfortunately, I think that the software/hardware distinction is ambiguous:
The word “turned” suggests that this is a modification to existing phones. Lucius also says “every phone in the city”, which is impossible if you have to upgrade all the existing hardware. (You might get good coverage, but not complete coverage.)
That would suggest a software patch, probably distributed virally or through the cellular carriers (more on that shortly).
On the other hand, this is the first time Lucius has seen the technology. Anything he says about it is necessarily a guess; he doesn’t know how this actually works, or he would have tried to stop it. Custom hardware is very plausible.
Further, as your answer on What is the time frame for Batman Begins, The Dark Knight and The Dark Knight Rises? attests, The Dark Knight is set in 2008. In the real world, I doubt this level of monitoring could be achieved with 2008-level phone hardware. In the real-world, he’d need to have added custom hardware for this to work. (So how much does Batman-world tech mirror the real world?)
How was it distributed?
I don’t know if Wayne Enterprises were a major phone carrier in Gotham (it wouldn’t surprise me, but I can’t find canon either way), but they might have some good links. At the 59 minute mark, there’s this very telling conversation between Bruce and Lucius:
Lucius: Did you reassign R&D?
Bruce: Yep. Government telecommunications project.
Lucius: I wasn’t aware we had any Government contracts.
Bruce: Lucius, I’m playing this one pretty close to the chest.
I can’t find anything else in the film that this conversation might be referring to, so I assume that this is Bruce reassigning R&D to build his large-scale sonar device. The “Government project” line suggests that he’s using his political influence to force this change through, so nobody is objecting. (Or at least, not loud enough to make a difference.)
There isn’t more detail on the Government’s involvement. I doubt they would allow him to spy on everybody in Gotham, so there’s probably a smokescreen to hide the true purpose from the officials. Or perhaps Lucius is right: the reason he doesn’t know about the Government contracts is because they don’t have any, and Bruce is going behind their backs.
Batman Wikia
The Batman Wikia article about the lenses says that it was a computer virus, but doesn’t source this assertion:
Batman later innovated the idea to an extreme, writing a virus that inserted the program into every cell phone in Gotham
It also alludes to an interview with Christopher Nolan where he might have discussed the lenses in more detail, but it doesn’t provide a link and I haven’t been able to find it.
When asked in an interview along with Christopher Nolan, Christian Bale said that the device was put into the cowl by Lucius Fox, who first invented the gadget, and it was part of his entire suit which helped him see better in the film.
