Say I want to carve a spoon from wood that I find, are there any trees I shouldn't use due to their toxicity? Are any that are particularly easy to carve or hardy?
I have to say that "eating with" falls under the same rules as "eating". Don't go out in the woods and put something in your mouth unless you know exactly what you are dealing with.
Specifically avoid the following (If it's listed here it has at least one poisonous variant. Since tree variants are difficult to distinguish, it's best for amateurs to not try these:
Anything you are not certain of is not safe. Plants develop poisons as a defense mechanism. The fact that you're not eating it helps a little, but when you use the spoon it will be in contact with your food, which will absorb and exchange with the wood. Heat, moisture, loose pieces, sucking... many ways to get a bit of some toxin in your system. And why take the chance? If you're not sure, just eat with your fingers and the next time you hit town buy something safe.
All that being said, generally woods which are safe for smoking, such as apple, hickory, alder, and maple, will be safe for utensils.
Also bamboo is fairly common in much of the US now, easily identified, and safe to use.
Some varieties elder may be safe
Lime wood is used by carvers as it is very soft! I can recommend it too, personal experience. And it is not poissonous of course.
My friend is using the wood from European elder to carve pipes. Its wood was traditionally used for this purpose. I haven't found any information on elder wood to be toxic (the bark can be though), but if you want to be sure, continue with your research.