A good resource for just about everything you need to know about making paddles is this book, available here at the WCHA store:
http://store.wcha.org/Canoe-Paddles-A-Complete-Guide-to-Making-Your-Own.html
There's a good discussion RE: pros & cons of different woods, and different ways to build them.
I'll suggest that the particular variety of wood for a first paddle is more dependent on what you want the paddle to
look like, rather than any features of the wood itself. Maybe choose a wood that matches the canoe's trim? Cherry & walnut make fairly lightweight paddles that look great, but the wood costs more than ash or spruce... which also make nice-looking paddles. All of these are fairly easy to work, as opposed to hard maple, for instance. I'd avoid basswood -- it's very lightweight, but doesn't hold varnish well, so it needs a lot of maintenance. Many of the paddles that I rehab for people are basswood, and the lack of maintenance really takes its toll on their appearance.
It's very important to keep your cutting tools very sharp, whether they're hand or power tools. I bought extra irons for my spokeshaves, so I can keep working when I'm on a roll, and stop to sharpen when I choose, rather than when the tools need sharpening. Whatever works for you...
By all means, post questions, and pictures, too... we lke pictures of paddles as much as we like pictures of canoes...