First you'll need to learn a programming language, at least to the point of loops, input/output, and graphical user interface (i.e. buttons, etc.). You probably could teach yourself this with a good book for newcomers, but I'd recommend taking a class if it's possible, either at your local school or computer store. Programming languages are far too difficult to jump right in for the first time and make a cool program.
As to which language, I've programmed in Visual Basic and Java, and I'd recommend Visual Basic (6.0 or less) if you're looking to do things with buttons. In both graphics and general syntax, I've found VB to make more sense (others may differ). Unfortunately, Microsoft has been suppressing VB in favor of their new, more Java-esque VB.NET, so it may be difficult to find a copy.
I'm an amateur at programming, not an expert, but Tic-Tac-Toe is one of the programs I've made. My most complete version is in Visual Basic. It has artificial intelligence for both the X's and the O's, with only one minor error where the AI doesn't make the smartest move (I plan to fix that eventually). That was the first AI programming I ever did and it took
forever. The first major difficulty is the logic of figuring out the best move in every possible situation (making a Tic-Tac-Toe program will make you a better Tic-Tac-Toe player), and then programming it in efficiently. Then I had to fix all the situations where the AI would put an "O" where there was already an "X" or the AI would play an "X" when it was playing "O" or something like that. Error-catching is a huge part of making a program - if it weren't we would have a CivIV Bug Reports subforum here.
Recently I've been rewriting the program in Java. I've taken a slightly different method in telling the AI what to move this time, and I
think the AI will play even better this time. I'm also planning to implement difficulty levels this time. Even with VB code to start from, it's still very difficult to get everything working correctly, and just one typo will result in the computer, for example, filling in the second box down on the right rather than the first down on the right. If I remember correctly, I've completed all but one major method for the AI playing "O", and none yet for "X". Another problem with my Java version is I'm not sure how to make sub-classes modify the buttons of super-classes, so my Java program is far less object-oriented than my VB version.
Both of these programs took several weeks to complete (not working on them full time, of course, but 45 minutes or so a day...8+ hours).
Other possible trip-ups in Tic-Tac-Toe included the AI not making a move because I missed a possible situation, and the AI hitting an infinite loop trying to find best-fit square. So I guess I just gave a bunch of examples of how Padma's second paragraph applies to Tic-Tac-Toe

.
My other finest completed programs include a ratings calculator (featuring 3-D arrays), a Wheel of Fortune game without a wheel (graphical difficulties), a Minesweeper variant (special thanks to Wingdings font), and a one player v. computer game of Chemin de Fer (the version of baccarat James Bond plays in the book Casino Royale). The Wheel game needs significant improvements to match the TV show (not including graphics), and I hope to add more players to Chemin de Fer, but they all are error-free
for now. Emphasis on "for now" because I remember when I showed a friend the Wheel program and he uncovered an error within about 30 seconds. That error has since been fixed.