If I sell a fossil that I found on my property, do I owe tax on the proceeds? How would I figure my basis? I “bought” the fossil with the land, so is my basis the cost of the land?
do I owe tax on the proceeds?
Yes. It's income when you sell something for more than you purchased it for. (Your primary residence is an exception.)
is my basis the cost of the land?
No, because you're not selling the land.
Consider this: you buy an old house. In it you find a antique table buried under a pile of junk, and sell it for $10,000. Is the cost basis the price of the house? Of course not. The cost basis is the amount of time and effort spent in making the antique table sellable. If all you did is dust it off and sell it to nearest antique dealer then your cost basis is $0. If you had it appraised, fixed up, etc before sale, then those expenses are deductible expenses.
The fossil is no different.
You talk about a "basis" when you are selling an investment. If you buy a stock as an investment and later resell it, the original price of the stock is your basis. Basis can get complicated when there are other costs involved, but it's really not what's relevant here.
You didn't buy this fossil from a dealer as an investment. This is more like an ordinary business. Suppose you made bird houses in your home and sold them. The cost of your home has little to do with your taxable income. (I'll get back to this in a moment.) What matters is what you spent for the wood to make the bird houses, the tools, supplies, etc, plus any other expenses, like advertising, maybe paying an accountant to manage your books, etc.
Similarly with the fossil. Did you have any expenses in finding or selling the fossil? If you were just walking through your backyard one day and tripped over it, then you had zero expenses in finding it. If you hired a geologist to tell you where you are most likely to find fossils, and bought or rented special equipment to dig it up, then those are valid expenses. Did you pay someone to clean it up and restore it? How did you or do you plan to sell it? Did you spend money on advertising? Pay a lawyer to write up a contract? Etc.
The only relevance of the cost of your house is if you used some portion of the house as an office or workspace, you may be able to claim a deduction for that. That's a complicated deduction so I won't go into the details here.
Unless you bought the land for the purpose of hunting for fossils on it, or for some other business purpose, you'd have a hard time claiming a deduction for the cost of land. If you bought it with no expectation that you were going to find fossils, you just expected to use the yard to play football with your buddies or have backyard parties or whatever, then it's not a business expense.
I should note that if you made only trivial money selling the fossil, like if you sold it to your neighbor for $10, I just wouldn't worry about reporting it. No one cares. I'm not sure if there's a law about the minimum income from a business before you have to report it, but the IRS doesn't go after people for pennies. But if you sold it to a collector or scientific institution for thousands of dollars, yeah, you'd better report it.
Basically you are in the "fossil hunting" business, and should file a schedule C. You should investigate all the sorts of things you can deduct on a schedule C.