We are creating some sample data for an application and we want to get
a complete list of all towns and their respective state in the USA.

There are several sources where you can pay for the list, but is it
available somewhere for free?

Thank you for your interesting question. The US Gazetteer Place and
Zipcode files (made from census data) are available for download here:

http://www.census.gov/geo/www/gazetteer/places2k.html   (2000)
http://ftp.census.gov/ftp/pub/tiger/tms/gazetteer/      (1990)

Specifically, you probably want:
http://www.census.gov/ftp/pub/tiger/tms/gazetteer/places2k.txt
or alternatively, for 1990 census data:
http://www.census.gov/ftp/pub/tiger/tms/gazetteer/places.txt

"The place file contains data for all Incorporated and Census
Designated places in the 50 states, the District of Columbia and
Puerto Rico as of the January 1, 2000. The file is plain ASCII text,
one line per record.

Columns 1-2: United States Postal Service State Abbreviation 
Columns 3-4: State Federal Information Processing Standard (FIPS) code
Columns 5-9: Place FIPS Code 
Columns 10-73: Name 
Columns 74-82: Total Population (2000) 
Columns 83-91: Total Housing Units (2000) 
Columns 92-105: Land Area (square meters) 
Columns 106-119: Water Area(square meters) 
Columns 120-131: Land Area (square miles) 
Columns 132-143: Water Area (square miles) 
Columns 144-153: Latitude (decimal degrees) First character is blank
or "-" denoting North or South latitude respectively
Columns 154-164: Longitude (decimal degrees) First character is blank
or "-" denoting East or West longitude respectively"

Since this is a lot of extra information, for your convienence I have
arranged this into new files. If you want only all the places
technically classified as towns (since that was the wording you used
in your question), I have arranged that seperately too, for each set
of census data. Also, I have put up two versions of the more complete
files (containing cities, towns, zona urbanas, etc.); the one without
spaces can be readily imported as CSV (comma-seperated values) into a
spreadsheet or database program of  your choice.

* Using the 1990 Census data:
http://bookface-ga.tripod.com/1990_towns_only.txt
http://bookface-ga.tripod.com/1990_with_spaces.txt
http://bookface-ga.tripod.com/1990_without_spaces.txt

* Using the 2000 Census data:
http://bookface-ga.tripod.com/2000_towns_only.txt
http://bookface-ga.tripod.com/2000_with_spaces.txt
http://bookface-ga.tripod.com/2000_without_spaces.txt

Additionally, you can check out a well-indexed list of places here:
http://www.placesnamed.com/


Hope this proves useful.

Excellent Answer.  Thanks for the additional data processing :)

A word of warning regarding Census data:

No two states have the same definition of "town." The census
categories closest to what you are looking for are probably "place"
and "minor civil division." While the entire country is divided into
minor civil divisions, not every part of the country is in a "place."

A "place" can be either a municipality or a compact community without
its own local government. Just because a state considers something to
be a "municipality" does not mean that the Census Bureau does. For
example, the bureau might consider the New England Town of Smithville
to be a "minor civil division," not a "place." The bureau might define
the "place" of Smithville as the unincorporated community around the
center of the town. Therefore, the "place" of Smithville will have
fewer people than the town as a whole.

A "minor civil division" is a first-level subdivision of a county (or
parish in Louisiana or borough in Alaska). In Northeastern and
Midwestern states, MCDs usually are called "towns" or "townships" and
have their own government. In the South and West, MCDs are usually
just administrative divisions of a county, such as electoral
districts. A municipality might be its own MCD, part of an MCD or part
of more than one MCD.

As you see, the simple question of "Where do you live?" can be quite
complicated. For most purposes, the "place" category will suffice.
However, if you need to have every address in the country in a
particular "town," you will need to look at MCDs instead of or in
addition to place.

Matt