Frankly, I would start with good old fashioned pencils and paper. You don't want the learning curve of software hampering your creativity. Not speaking for the others, usually logos are hand-drawn anyway before they are scanned, traced, and refined in the software. That said, as far as software goes, I would suggest a vector program, and rather than invest in Adobe Illustrator right off the bat, go with Inkscape, which is free and has all the capabilities you would need as a beginner. The concepts of paths, curves, fills, etc., are pretty fundamental to any of the vector programs.