I'd call the Bay County, Okaloosa, and Walton County Sheriff's department and fire department.
They are the ones who patrol the beaches in PCB and west of there. The fire Department also does the beach/lifeguard patrol in the Destin area, however, they don't have a standard normal Lifeguard duty during December.
Calling ScubaTech and Emerald Coast Scuba in Destin might be a good idea.
Make up a flyer, put a picture of the gun (download one from the web) with your name and phone number(s) and REWARD in big letters on it and fax it to these locations. Ask them to put it up in their shop/stations for a few weeks. maybe you'll get lucky.
EDIT: Make it as a PDF or Word Doc also so you can email it out. Find out anyone who has a charter operation, fishing or diving, and send it out via email.
Also post "lost/reward" on your local Craigslist.
Mike