Well, in my case, before I got accepted into Digital Media I had to present a folder of various 2D and 3D projects. Therefore, it's imperative that you try and get some of that formal training yourself, which isn't hard.
It really depends what you're looking for. Vector and raster art are both big fields to work in, so I recommend programs like InkScape(Adobe illustrator) or Gimp 2.0(Photoshop).
To do graphic design, you really need to know art. The best way to do art is to look at art from other's to create a personal taste (www.conceptart.org)/(www.deviantart.com) and then do it yourself! Study a lot from real-life and models so that, when you actually get to doing things digitally and free-form, you actually have some knowledge.
If you want to learn photoshop, there are a wealth of websites to do this with. Tutorials on DeviantArt are probably the most common source, but I would also recommend:
http://www.photoshoplady.com/
http://www.1stwebdesigner.com/design/30-useful-sites-where-to-submit-your-tutorials/
The second link is a bunch of links to photoshop tutorials. You will definitely figure out how to use photoshop and nifty techniques with those!
Some fine (free) 3D applications would be Blender and Google SketchUp, the latter was used to create my 3D model for the college entrance. I hadn't used it before, but found it to be intuitive and easy to learn.
These are the basics. You can always branch out to game graphic design after you have some of that formal training. There are many pixel editors if that's your kind of thing. If you try to jump into free-form game graphic design without any sort of training, then you will likely produce sub-par results that will simply demotivate you until you don't want to do any more.
Of course, you can be stubborn and try to do it anyway. Best of luck in any case ^^