I need to know how to obtain a .gov domain name for the city of
Lithonia, GA (City Hall & Police Department). I am being contracted by
them to setup their computer systems / servers / web presence
correctly. With .gov domain names, do they have to be hosted on
goverment servers, or can they be hosted on any normal web server?

Dear Technik, 

You cannot register a .gov domain name for a township at the local
level. .gov domain names are restricted only to the federal
government. You can contact the registration site at:
Dotgov.gov
<www.dotgov.gov/> 
(Note: the site was not up when I last checked it, so just in case,
I'll give you the cache:
Google cache for Dotgov.gov
<http://216.239.59.104/search?q=cache:2I5TR0HRk0gJ:www.dotgov.gov/+&hl=en>). 

Georgia-based governmental sites have a different TLD suffix, .ga.us. For example: 
City of Atlanta
<www.ci.atlanta.ga.us/> 

You can register a .us domain name in every place and host them on
every server (in the US).

Here are the conditions from NameScout: 
Who can register a .US domain name?
<http://www.namescout.com/faq/help.asp?qid=296&lang=en> 

More here: 
Directi
<http://www.directi.com/products/domain-name-registration/tld/us/> 

Here is a list of registrars that can take a .us name: 
.us domain registration - neustar
<http://www.neustar.us/register/index.html> 

Please note, that locality names have special provisions: 
Neustar: Locality names
<http://www.neustar.us/register/locality.html> 

Your lovely state also provides you with some information on
registering a city/fire department:
What's in a name
<http://www2.state.ga.us/domain/What_is_a_name.html> 

Here is their domain registration service: 
"State.Ga.US" & "TEC.Ga.US" Domain Registration and Information 
<http://www2.state.ga.us/domain/> 

I hope this answers your question. Please contact me if you need any
clarification on this answer before you rate it.

Great Research!!! Thanks for the help!

Thank you for the rating and the tip!

Sorry, but this answer appears to be incorrect.  Non-federal govts. do
appear to qualify for .gov domains.  I have at least one example of a
non-federal .gov website: www.nyc.gov (I live in New York City).

There's also www.ca.gov, www.illinois.gov, www.colorado.gov . . . 
And some municiplaities: www.phoenix.gov, www.sandiego.gov, www.houstontx.gov . . .

Search strategy:
"state of" site:.gov
"city of" site:.gov

The elegibility requirements can be found here:
http://www.dotgov.gov/help_qualify.aspx