The Rule Book
This is where the bulk of the game explanation needs to go as well as all special case situations that came from your play testing. Most players won't want to read a wall of text to figure out how to play a game, especially when they are playing it for the first time. Also, I don't think many players want to have to study a game they just bought before their friends come over to play it for the first time. The first thing to do to alleviate these problems is to have clearly separated sections explaining each aspect of the game as well as a section for explaining the general flow of the game. Generally, you'll want the following sections: Objective (how do you win?), Game Components (explain each component, which also builds a vocabulary for talking about your game), Board Layout (what should the board look like while playing?), Game Flow (how does one turn or round play?), and then detailed sections of each phase of a turn.
For ease of clarification, there should be plenty of pictures (Game Components section has pictures of each of the pieces, Board Layout has a big picture of the board) as well as examples (Jimmy draws 1 card and then plays an Action card). The examples should be either off to the side or somehow separated from the game explanation (italicized or put in a different box) so that players who don't need further explanation can skip to the next part they care about easily.
If this game is a small card game, the rules might be either a card itself or a very small sheet of paper (both Fluxx and Bang have rules like this), which makes it even more important to have good layout and lots of pictures, since you have such limited space to describe the rules.
Helper Cards
Even if a player has read the rule book and fully understands the game, it is a pain to have to hunt through the rule book if you forget something of the game. This is why a lot of games come with cards that display some key information used repeatedly by a player. This way, multiple players can have this information in front of them at the same time. For example, Settlers of Catan has a card that illustrates the cost of the various things to purchase. Bang has cards that quickly describe what each symbol in the game means. I like to make Helper cards that describe the game flow so all players can see what is supposed to be happening. Some games like to put this information on much bigger cards that every player already needs. For example, Tales of the Arabian Nights has a Character mat for each player for the player to store their tokens on. This mat also has lots of information about how the game plays.
Game Components
In many cases, the game components themselves can teach the player how to play, sometimes without them even realizing it. The simplest way is by having outlines or colors on the board that match specific tokens. This way, the players know where to put specific tokens. Another simple way is in a game with cards, the cards themselves have a brief explanation of what they do. My favorite example of this tacks on another method of teaching. In the game Bang, not only do the cards tell you what they do (with a few exceptions where you have to look them up in the rule book), but they do so with a set of symbols that are universal to the whole game. If you ever see a hat with a line through it, you know that card counts as a Miss, no matter what other effects it has. As stated above, these symbols are explained on Helper cards for all the players. The reason this is so nice is that it gives the cards more room to display art that gets the players in the right mood/mindset/character for the game. It also means that when any expansions come out, cards can be added with combinations of the symbols and players will immediately know what they do.
Ultimately, all of these methods require a good graphic designer and/or artist since ultimately it's all about the layout. If you can utilize these ideas during the prototyping phase, it will significantly help things out, but it's not a requirement since you'll be there for when those prototypes are being played.