Everybody else's ideas are best, because they seem to have been written by people who actually know something. That won't stop me from throwing in my 2 cents, though
You may want to play with PyGame (
http://www.pygame.org/) a little as you get the basic ideas of game programming down. It relies on SDL (
http://www.libsdl.org/), a cross-platform, open source multimedia library. Don't let that scare you off, though. SDL and PyGame both get used for making games in the real world - even in the Windows world that I hear about on occasion.
The big advantage of PyGame is that it is written in Python, which is a very easy language to get up to speed on. You said you hadn't programmed any games before. I don't know whether that also means you hadn't done much programming at all, but Python and PyGame are worth considering.
There are several tutorials available at the PyGame Web site, and I recently bumped across a book on using Python for game programming in my local giant mega-bookstore. I didn't have time to take a good look at it, but you could probably find something out poking around at Amazon.