I have an acquaintance who claims that her grandmother told her that a
hurricane in 1908 killed all the native palm trees along the Gulf
Coast of Alabama and they never came back.  I have lived here, Orange
Beach/Gulf Shores area for nearly thirty years and do not believe
there were ever any indigenous palm trees to this area.  All of the palm
trees in this area have been brought in and planted around homes, condominiums,
hotels, etc.  There are certainly native palmetto ferns, but I do not
believe there were any native real palm trees.  I am looking for an
authoritative definitive answer to this question.

http://www.pacsoa.org.au/palms/Rhapidophyllum/hystrix.jpg

http://www.raingardens.com/psst/articles/stxpalms.htm

hapidophyllum hystrix (NEEDLE PALM) is native to southern Georgia and
Alabama, extreme southeastern South Carolina, extreme southeastern
Mississippi and all but the most southern region of the Florida
peninsula. It is an endangered species in the wild, originally never
that abundant in any given locality, and vastly underexploited as an
ornamental/landscape subject. It is a clumping or suckering palm with
very short or sometimes apparently non-existent trunks and usually no
more than a total of three. The growing points are covered with fibers
and a few very long and sharp gray to black, mostly upward pointing
spines, which fact gives rise to both the common and botanical
(scientific) names. The little palm has wonderful leaves that are
long-petioled, with the leaf blade (lamina) forming a semicircle of
very deeply divided yellowish green to dark green (mainly depending on
how much sun it gets) segments that almost always exhibit a white or
grayish midrib. It grows in sun or shade but looks its best, we think,
in at least partial shade which makes the petioles even longer and the
color of the leaves a deeper green. Individual plants can attain a
height of about eight feet and a width of 12 or more feet. There are
few small palms that are better suited to planting under a tree
canopy. It is not very drought tolerant, but will survive such
condition and it likes a fairly decent and humusy soil -- two
requirements somewhat difficult to come by in most of southern Texas.
Some consider this species to be the world's hardiest to cold; if it
isn't it is definitely the second most hardy.

Hey, I wasn?t around for 1908 hurricane, but for a couple later on. 
Are they still showing people the painted spot of blood where the
officer at Fort Morgan died?

Clint34-ga beat me to a comment, but

This site tells all about palms that grow in the Deep South, and
indeed the Cabbage Palm is a native plant, and has a trunk.  I agree,
that most of the other natives are more what I would consider a
palmetto, and your friend?s gran was probably also thinking about
palms with trunks.  Interestingly, the article says that the cabbage
palm is often one of the few trees remaining after a hurricane, but
maybe if even they blew down, that was a measure of that hurricane?s
strength.
What I don?t know is how palms reproduce  - if they aren?t coconut or
date palms -  so it could be (?) that if the native ones all toppled,
they did not come back.  So on one point you would be right, that all
the ones you see have been planted and may be non-native varieties. 
Anyway ?

http://www.ces.uga.edu/Agriculture/horticulture/Palmreader.html#Some%20Palms%20You%20Can%20Grow

palm tree native gulf coast    as a search found 98 000 hits, so maybe
you can find more of interest.