We know that we can't control what people do on their phones/tablets/personal pc's. The issue is when these people use city owned equipment along with their personal hotspots/smart phones to bypass security we have in place to protect our network.
Firstly, it'd be very easy to create a simply bit of software that'll monitor the airwaves for new networks that show up and report them back. You can setup applications such as netstumbler that'll log the time and date of the networks as they come and go. That could be sent off at the end of the day for example.
A better bet would be to use something the common Linux wireless air* tools, usually used to crack networks, to monitor the active networks, including networks that do not broadcast their SSID and you'll also be able to see what devices are connecting to what network, by their MAC address. This would be proof that such dept hardware is connecting to say a Nokia cell phone acting as a access point.
However, its unlikely that you'll be able to block or do anything about people using their own devices to setup access points if they really wanted to.
What I would suggest is looked at enforcing a network policy on the dept machines so they can't join additional networks. That'd be the best option as even if the employees setup their own AP, they wouldn't be able to use the dept machines to connect to them (without a lot of spoofing, but that is possible anyway)