Start with a low Janka harness wood like basswood. The red cedar is higher Janka, but still carves nicely though prone to chipping if you do not outline with a blade, so that is a good option too. The Birds Eye Maple was a lot tougher, I had to use my mallot for 80% of the carving since it is more than double the Janka of cedar, so I would stay away until comfortable and you have better tools, even with my good gouges, I had to stop and strop my gouges more frequently.
Next tip... have a 'squared' (rectangle) piece of wood to cut from so it fits in your vice, (and after cutting out becomes your holding support) then after laying your pattern, carve your spoon bowl first, this way you have full support from the board, then drill, do inner cuts, then the exterior. Finally, carve and shape the rest.
I did not do it this way at first and actually broke one of the more delicate pieces because of the pressure of my vice. Thus you see how I had to jury rig support in the vice.