Behind the Name: The Most Popular Names has popularity stats on first names going back to the 19th century and including several different countries (only the US stats go back as far as the 19th century though). They also have a site for surnames:
Behind the Name: The Most Common Surnames - the data for the US is the same (from the 1990 census) but they have data for other countries too.