You're on the right lines - I only ever make logos in Illustrator. That way they can be scaled to use on anything from business cards to billboards. I used to use all sorts of programs when I was starting out - Paint Shop Pro, GIMP, Fireworks - to make logos, but they all had compromises somewhere in the workflow.
Illustrator has a learning curve, but it's worth climbing up it for logos etc.
If I only had Photoshop, I'd be working at 300dpi to a Letter-paper sized logo (minimum), saving in PSD format and exporting as GIF/PNG as needed.
HTH,
Pete.
I'd highly recommend using some kind of vector-editing software for logos. If you can't get Illustrator for now, go ahead and download inkscape (http://www.inkscape.org). It's free, and works well.
Ahhh. It really is worth it, and for logos, it's really the only way to go. I don't know if it's always included, but when I bought the creative suite, it came with a dvd with all kinds of tutorials on it. That's an easy way to get started. Also, you might try Lynda.com, which has all kinds of graphics tutorials, some for free and others with subscription.
When you are making a logo for a business, what size logo do you make? I try to make them really large so that they can then shrink them later if needed because I make them in photoshop rather than in illustrator (I'll get there eventually) any suggestions?