As many of the other answers point out, software is just a tool to bring your concepts and ideas to life. So, most importantly, make sure that you are very well versed in creating unique concepts. Always start with sketches, as they help you to explore ideas quickly and possibly come up with things "by accident," which can often lead to some of your best ideas.
That being said...
Photoshop - great all around tool, the MacGyver of design tools
Illustrator - great for vector work and illustrations
InDesign - great for print layouts and multi-page projects. The standard in the print industry
Dreamweaver - helpful for wysiwyg web design, although not necessary. Depending on your coding background/experience, many people just do the coding by hand.
After Effects - great for motion graphics. If you are into video and motion graphics this application is EXCELLENT and is very powerful
Flash - great for web application design (some people will refute this) and animation. Great in small doses but is often overused, esp in web design.
Fireworks - helpful for web graphics and slicing, but not essential
PowerPoint 2010 - Although PowerPoint has gotten a very bad rap over the years for its misuse and terrible presentations(the users fault), the new version of PowerPoint is capable of making some graphically stunning presentations, and is fairly easy to use. Check out this great example of what is possible.
Expression Web - helpful for web design. Very similar to Dreamweaver, but offers some more optimization tools.
Autodesk Maya - Amazing 3D rendering software. Most places don't specialize in 3D, but this can really help to give you an edge against another applicant. It can also help a design firm to have an extra asset on their team. Be forewarned, there is a bit of a steep learning curve
Again, the bottom line is to have a strong background in graphic design. The ideas far outweigh the means of expressing them, and any piece of software can be learned over time.
If going for a job in print: Photoshop, Illustrator and InDesign are a must. The entire Adobe suite recommended.
If going for a job in web: Photoshop, Illustrator and Dreamweaver/Expression Web are a strong recommendation.
Hope all this helps.