When a customer makes a payment with a credit card, does the store
automatically get the customer's address from the credit card company?
or would the store have to ask the customer for his/her address like
on many web sites?

Untlimately I would like to get some demographic estimates for the
customers. If I don't have the address, is there a service where I
could submit a list of credit card numbers and get back demographic
characteristics?

No, the store doesn't know anything about the customer from the credit
card. (data protection and all that) The store would have to ask for
the address from the customer.

The reason many websites need an address is for validation with the
credit card company. The credit card company ask the store for the
address and if it matches their records everything is ok, if not the
credit card company will refuse the authorisation for the payment.
This doesn't happen with every sale (otherwise you would get asked for
your address everytime you go into a store!) however it will happen on
a random number of transactions, and also unusual transactions such as
you use your credit card once for something very small, then suddenly
in one day start making huge transactions.
It works this way around so the credit card company is never giving
out information about their customer, they will either authorise the
payment or not depending on the information given, they won't tell the
store the address.

There aren't any services which would allow you to enter credit card
numbers and get demographic information back as this would be breaking
the data protection acts (I am in England, but I am certain America
has them too)

Actually, 
If you are the person in charge of the transactions (from the credit
cards - like the store owner) you can go to lets say "American
Express" & have them give you a report on the demographics of your
customer.  I've done it before & its very interesting.