A logo is all well and good but keep in mind that once it's done ou can be stuck with it. Some of the best logos in the world are extremely simple and subtle.
I'd suggest that you think long and hard about what you might like. Many very successful businesses thrive with a simple text line naming their business. Adding a drop shadow to your business name with a nice background can work wonders.
Also keep in mind that graphics should be very carefully prepared since a graphic logo should really be part of your overall branding. This means it has to feature on all of your business stationary - letterheads, cards, compliment slips and so on. Graphics printing is a whole new world and it can get quite complicated to get good results. The more detailed your graphic and depending on which colour cheme you choose you could end up by needing a program that can output a bit more than your bog standard bitmap or jpeg.
You could do worse than start simple with just the business name, perhaps give it a drop shadow and border.
Regarding software, any of the mainstream image editors will do the job. I like and use Ulead PhotoImpact, Jasc Paint Shop Pro, Macromedia Fireworks and Adobe PhotoShop in about that order. For serious print design work I lean very strongly towards Quark and Adobe InDesign, but they are overkill for most users.
It isn't the software you use, it's normally how you use it and a good idea from the outset, properly implemented, works wonders. A bad idea from the outset usually only gets worse as you try to get it working for you.
My own 'logo' is simply text presented in a certain way. No fancy graphics or banners for me, and I can't say my business has suffered in any noticeable way because of it.
All the software titles I mention above have 30 day trials available for download and you often find them on magazine cover CDs.