I cannot recommend highly enough Hiroki Mori's "The Interactive Way to Go" site, which walks the user through all of the following basic rules by allowing them to play through the necessary continuations.
There are two players involved in a game of go, and each has a set of "stones", which they take turns to place on the board. Stones are only placed, never moved, though stones can be removed when the are captured (see liberties and capturing below). One set of stones will be black, and the other will be white, with black taking the first turn when the game is even (see handicaps below).
The board is normally made up of 38 intersecting lines (19 horizontal and 19 vertical) which comprise to make a grid of 361 intersections (bearing in mind that in Go, stones are placed on the intersections, not the gaps between the lines). This is called, intuitively enough, a "19x19 board". There are also standard board sizes of 9x9 and 13x13, which are normally considered to be boards for beginners (though strong players still use them for quick tactical games, the style of play required is different).
Picture of Go board with stones
Liberties and Capturing
To capture a stone, it must be completely surrounded on its horizontal and vertical surrounding intersections - that is, the intersection above, below, to the left, and to the right of the stone to be captured. Whilst these positions are empty, they are considered to be "liberties" for the stone to be captured.
Stone in the middle has 4 liberties
Stone on the edge has 3 liberties
Stone in the corner has 2 liberties
Once all the liberties are taken by the opposing player, the stone is "captured" and removed from the board. If the game is being played under Chinese rules, the captured stone is returned as it is not counted for scoring. If the game is being played under Japanese rules, the captured stone is kept by the capturing player as a prisoner, used to adjust scoring at the end of the game.
Stone with only 1 liberty White to play
White captures the stone
If stones are connected horizontally and vertically to other stones of the same colour, they form a "chain". Chains can still be captured, but once again all of the liberties need to be played on by the opponent, for each stone within the chain.
Chain with only 1 liberty White to play
White captures the stones
There really aren't many illegal moves in Go, you can really put a stone anywhere that there isn't already one. There are only two rules that forbid you from playing a stone in a certain position. The first is playing a stone where it would be captured, either as a single stone or adding to a chain with only the one liberty. As this would technically result in the stone being dead, it is not permitted. The exception to this rule is when the stone actually makes a capture - in this case, after the capture the stone would no longer be dead, and therefore the move is permitted.
Black to play "X" is an illegal move
With this move Black can now play at "X"
White extends elsewhere and Black captures
The Ko rule
The second "illegal move" rule is the "Ko" rule. One of the disadvantages of the previous rule exception is that it can allow games to continue infinitely as demonstrated in a continuation of the above position:
Black captures again
White recaptures again Position repeats indefinitely
To combat this, the Ko rule was created to prevent the immediate repitition of a position on the next move. So if black captures in the above position, white cannot immediately recapture. If he plays elsewhere, black can either respond to white's new move, play somewhere else entirely, or fill in the hole left by the ko threat. If black does not fill in then white can recapture and the roles reverse. Eventually the position will get filled in when it is considered to be the most important move left to play on the board. The above situation could pan out as follows:
White to play Cannot recapture
Both Black and White play elsewhere
Ko rule no longer applies and White recaptures
There are more complicated "Super Ko" rules that are not covered in this tutorial as they are not implemented on this site. These rules are designed to prevent the exact repetition of a board position at any point in the game, normally a result of a very unusual game status such as a triple ko (where there a three significant ko threats on the board, and they can be played in sequence to create the same position again and again). For completeness read the following links from Sensei's library that discuss the Ko and Superko:
Superko - This is the basic overview of superko on Sensei's library.
Triple Ko - This is the basic overview of triple ko on Sensei's library.
What's wrong with Super Ko - This is an excellent, if complicated, discussion on the implications of super ko and the situations that give rise to it.
One of the great advantages of the game of Go is the ability to balance (to some degree) games between players of different ability. Traditionally, amateur go players have a rank (also known as a grade) that determines their ability (see Ranks and Grades section). In a handicap game, the weaker players starts with stones on the board in predetermined positions, and plays as black. The stronger player then goes first with the white stones. On a 19x19 board, one stone is equivalent to about 1 grade in ability difference, and the maximum standard number of stones considered to keep a sensible game is 9 on a 13x13 or 19x19 board, and 5 on a 9x9 board.