I have a 3g-grandmother, Margaret Davitt. According to stories passed down in the family, she was born on ship in 1799, and was apparently orphaned on the ship or very shortly after arrival. The first record I can find for her is an 1834 marriage in Philadelphia. She died in 1859 in Illinois; I would love to find records for that also.
The information came from my grandmother's notes made in the mid-1930s, and was probably told to her by her father-in-law, Margaret's husband.
First off, the more information you have the easier this will be. You'll optimally want to know the:
...and any other information about the voyage you can lay your eyes on.
As far as I know, very few, if any, ship records exist pre-1800. These are spotty at best and rather difficult to locate. If you're (extremely) lucky and your ancestor immigrated through the port of Philadelphia, you just might find them in the NARA's M425, Passenger Lists of Vessels Arriving at Philadelphia, Pennsylvania, 1800-1882. However, these don't include everyone and it is highly unlikely that you'll find a 1799 ship in the 1800-1819 records. The reason I include this in my answer is that your date could be off by a year and your ancestor could have actually immigrated in 1800. This could be worth a shot.
Another more promising avenue is the local newspaper. If you know the port of arrival, you can find the local newspapers. If you don't know the date of arrival, you have a lot of searching ahead of you. If you have the month of arrival, or even the day of arrival, you can more easily pinpoint which newspapers you need to look through. This might take some time, but it is probably your best bet at finding the information.
Once you have the names of the local newspapers, you obviously have to find the specific issues you want. It all depends on the paper, but you might be able to find it online. If you can't find the newspaper online, contact the (current) local library, museums, and historical/genealogical society(ies). They might have the newspapers on microfilm or possibly the originals. This might mean you have to travel to the location to view them, but you might be able to order photos of the films you need.
There's no one way to find records that works all the time, which make genealogy a lot of fun, but hopefully this answer gives you some ideas to look into.
