I know there are a few similarities to this thread on free software here but I will mention some items based on your question knowing that my experience and preferences are different from many others. my experience is limited to only free stuff I have found but if I were learning from scratch I would:
watch some videos on Tinkercad and get a feel for navigating a 3d view, learning the concept of “extruding” shapes, “Grouping” shapes, subtracting from “Boolean operations” shapes to create new objects. This will give you a feel for what it is like in a 3D modeling environment. (Tip: you can also import an image to create a 3D relief carving as you mentioned above)
After this, I would move into something like Sketchup. you mentioned working with wood and Sketchup I believe is great for setting dimensions of your wood part and defining measurements. it is also quick and easy to learn for beginners.
After this I would move up into some programs that are a bit more complex like Blender (free download) or Onshape (Browser based like Tinkercad) They have the ability to produce smoother more higher definition objects which are difficult to produce in easier programs. They often produce high polygon count objects which means that they can have thousands of edges and faces (Smoothness) but then if you import those objects into sketchup or tinkercad, the objects get messed up or program fails. I think this is where you mentioned that you can sometimes tell which program a designer used when you see low poly or boxy looking objects.
If you ever do go to windows 10 platform, I am really liking that 3D builder allows me to suck in higher poly models and work with them like tinkercad without any degeneration.
This last item for me is not so much CAD but it seems like an essential tool for laser cutting and has been mentioned also 2 or three times. 123D make will be great for you to slice up your creations into laser cut patterns.
I have heard good things about the CAD that others have mentioned above and I would certainly give those a try if you are ok spending a few dollars.