well ive used hawthorn, ash, beech, oak, pine, maple, redwood, well seasoned yew, and a few other varieties too, (whatever i can find lying around in the new forest) basicly , if you understand the properties of the wood and modify any design accordingly you can get a spoon out of most woods, (and feel rather smug at your achievements!!) if its a floppy wood keep the handle and section where it joins the spoons bowl quite thick. i prefer seasoned wood or something like a log from the ground, its great when you turn a useless bit of wood that would otherwise rot away into sonmething useful. seasoned wood is better becase the grain is less likely to separate when you are 90percent finished as your spoon dries out, - which can lead to annoying cracks and splits in the handle with some woods.
look for woods with a natural kink in them and split them so you get a spoonlike curve in the shape of the spoon ( a flat spoon from a totally straight log isnt as good in my experience, its no easier to carve and isnt any good for eating with, thats why real spoons have a kink in them - mass produced wooden "kitchen" spoons are flat for one reason only,,as many spoons out of one log as possible.). splitting logs reveals any flaws like knots, which depending on your skill can be an interesting feature or a nightmare. you usually find knots in the middle of the bowl section of your spoon, which isnt reallly a problem if they are small.
when collecting i tend to split on site and leave behind the "non spoon half", a bit of crude carving on site also helps if you want to collect a few "blanks" and put them in your rucksack. ,,,you dont necessarily need an axe to split the wood if you have a good knife, but it helps if you do have a small axe as splitting a say, 3inch thick log with a knife, can bend or even shatter it if you are not very careful., once a split is started you can carve wooden wedges from another bit of wood with your knife to drive them into the split to aid you in separating the two halves. use another nearby log as a hammer if you like!
when youve split the wood and flattened off the inside half of it (ie, the heartwood) mark out the plan shape of the spoon with a pencil and carve to near the lines BIT BY BIT, (you can always use another spoon as a template), youll probably want to take some material off the back of the handle and toe of the sppon to helf you at this stage. (i hope that makes sense)
..then sand with coarse and then fine fo refine the shape. then its down to your imagination and skill!
the one thing i have found is that to get something nice and elegant you need to spend quite a while sanding away to get smooth flowing curves and symetry.
below is a link to a spoon i made from pine, a knot in the bowl is visible, plus other defects, which made a rather interesting spoon, start to finish about 4 hours over a few days.
good luck!
http://uk.pg.photos.yahoo.com/ph/adam_whalley2002/detail?.dir=4659re2&.dnm=8f46re2.jpg&.src=ph