Paleolithic Americans are roughly those folks that roamed the Americas more than 10,000 years ago. After the Paleolithic you slip into the Archaic Period, 3-10,000 years BP. These are very rough dates and the overlap between the Paleolithic and the Archaic maybe as much as 2,000 years. There are not many human remains from the Paleolithic and what there are do not seem to be related to any of the current populations that are labeled native Americans. The oldest grouping of Paleolithic Americans are the Clovis people. This grouping is done by the finding of culture remains with the style of fluted points called Clovis. They are roughly 12-10,000 years before present. How long people were in the Americas before then is still being debated. I would go with 18-20,000 BP at this point but keep in mind probably all the earlest sites are coastal sites, and they are currently under 200 to 300 feet of ocean.
Some intersting things about the Clovis points. First they are found all across north America with the greatest concentration being found in south-eastern USA. Secondly it seems this style of point spread across North America in about 500 years (as an comparison the bow and arrow took about 3,000 years to spread from the Eskimo(?) to Mexico). And thirdly there is a nice transition to a type of fluted point named Folsom. The Folsom is a lighter and finer worked point. My own theory is that the Folsom point was developed with the introduction of the atlatl spear thrower. The oldest remains of an atlatl are about 8,000 BP from Nevada, about a 2,000 years gap in my theory! And to add to my theory, I believe the Clovis and Folsom technology was developed to hunt mammoths, giant bison, and mastodons. After the extinction of these big mammals the high quality of flint spear points went to hell. Of course there were local exceptions (Dalton points) but never again would a flint design sweep across North America.
Of the mega-fauna hunted by the Clovis people mammoths and mastodons were the largest. Mammoths and mastodons are part of the Proboscidean family tree which also include elephants. There are about 6 species of mammoth, the one found with Clovis points is the Cloumbian mammoth (Mammuthus columbi). I don't think any Paleolithic points have been found in the Americas with woolly mammoth (Mammuthus primigenius) remains. However, Clovis points have been found with mastodon (Mammut americanum) remains in North America. The Manis site in Washington state and the Kimmswick site in Missouri are two locations. Though the mastodon is a member of the Proboscidean family they branched off the family tree about 20 million years before African and Asian elephants showed up about 5 million years ago.
The story of the Paleolithic Americans is still mostly unwritten. If someone had a few dollars to set up a foundation, with a website to collect all the published data, and digital photos of all the artifacts, in one location as a resource open to everyone that would be a start. (Of course this is true of so many fields. So much stuff just hidden away in museum drawers collecting dust. Why aren't all these collections availalbe on DVD's or the museum's website?)