The best software is Adobe Photoshop CS5.5 because that's the newest one. Followed by CS5, CS4, etc. etc. but only if you're already pretty good at Photoshop or are following tutorials and learning from them.
Personally, I use the GIMP. It's pretty hard to use for beginners, though. If anything, I'd suggest either GIMP or Paint.NET, as they're both free and powerful enough for what you need. Other tools that are good include Aviary's Phoenix I believe? There's also Sumo Paint. Both Phoenix and Sumo Paint run in the browser, so if you don't want to install anything, those are your best bets.
If you want to, I could make you one. I'd need more details, though, like which Pokemon you want on it, what you want the banner to say, etc.