Strategy for Raw Beginners (30 kyu - 21 kyu)
Just relax; it's only a game and you're only a beginner. Don't worry about winning or if you're not improving fast enough. Your game is an extension of your personality and emotion at the time of each move. Tensing up will only cause you to lose even when you don't have to.
If you aren't having fun then there is no point in playing. The more you let yourself enjoy the game the better you will become.
Rule Number 0: Play LOTS of games. Play during every waking moment that you can. Try to play people stronger than you. They will defeat you, but they should teach you, and show you how to become better as well. Play computer programs. They will defeat you, but they are always ready to play (you can find them by just looking online). Books do exist for the absolute beginner (Such as Learn to Play Go by Janice Kim), though their use is rudimentary. Get a better feel for the game, then go after the theory.
Rule Number 1: The best thing that you can do at this stage is play and lose the first 50 games as fast as possible. Play a move within 5-10 secs and see what happens. Should you stop and try to think about every move, stronger opponents will become frustrated and decline to play with you in the future. Think of it from their perspective: they wait and wait for you to play, and then they see a flaw in your play very quickly and play, only to wait some more. As you play more games in this manner, your intuition, ability to read ahead quickly, and ability to recognize threats will all improve very quickly. As an added bonus, stronger players will agree to play you more often and will show you new shortcuts and situations, helping you to improve even faster.
Rule Number 2: Territory comes first. If one of your stones is in atari, the best move might be to ignore it and aim for that tasty side dish. This is not always the case as individual stones can be important, but your intuition on this will improve as you play more games. It might be the case that you're trading the 1 point of territory and 1 prisoner for a 20-40 point side.
Rule Number 3: Do not be afraid to take risks. You don't understand the game enough at this point to say, "that is overextending myself". Just drop a stone in there and see how it fares. Do try to avoid doing so when you know that one of your bigger groups is in mortal peril.
Basic Strategy (20 kyu - 11 kyu)
Congratulations. You have reached a point that 50% of the people I've introduced to the game never reach. Rules no longer exist, merely ideas. This is the point where most people feel like an idiot because they are finally glimpsing the extent of the game. Stick to it and make it on to the next level.
Idea Number 1: At this point, you should begin your thought into the workings of the game. Try to avoid making the same mistakes more than twice. Don't stress if you do, just note it, and try to avoid it again. Begin to look at influence and how individual stones affect the area around them. Take a look at joseki, but don't take them as stone tablets. Play with them a bit, it'll help you understand why they were formed that way. Ask questions, and try to understand the answers.
Idea Number 2: Watch stronger people play. Many of the moves will confuse you. Aim for about 5 kyu ranks above you. That way the entire game won't blow over your head, but it will stretch your mind. Try to understand why they moved on from a fight, or why an "obvious" move wasn't played. Understand that these people are probably wrong about a lot of things, but they can take you to school and are worth listening to.
Idea Number 3: Tsumego: go problems of varying difficulty; they can be found online or in books. Start trying to solve them. They will vastly increase your fighting capability. Do not however take more than 60 seconds trying to solve them. If this is the case, they are too hard.
Idea Number 4: Read ahead and have some idea about how your move will affect the board. You should be reading about 4 moves ahead easily as a 20 kyu, and >8 moves ahead as an 11 kyu. Keep in mind Rule Number 1 from the 30k-20k range, and keep it short, but do look for the best move. You may be wrong, but just looking will help you improve.
Idea Number 5: Do not be afraid of moving in a different area of the board than the last move. There are many times when you need to do so, but watch for when your moves just aren't worth that much. When you see yourself fighting to gain tiny amounts, go and claim another section of the board.
Strategy for Variants
Beware that an illegal move can be a suicide one. Playing next to an illegal move often lets you decide whether it was because there already was a stone, or because it was suicide.
Play strong connected goups. You don't know that you're attacked until some stones are captured. Be sure that almost every stone will be discovered sooner or later by your opponent (and you're not told which one he discovers). The more previsibly you play, the earlier your stones are discovered.
There is no influence. What looks as a territory (such as a wall on the third line) might in fact be invaded (by a wall on the second line).
Divide and conquer is a viable strategy.
Kill while you still can.
This is a game where both players are the same color. It's significantly easier than blind Go as you have a reminder of each move. Don't think that this is easy though. If your attention slips, it's very difficult to regain where all of the moves are.
The key is to remember the patterns. You don't need to memorize each piece in a corner if you can remember that all of the moves fall under a certain joseki. Just keep running your eyes over the entire board reminding yourself of who all of the pieces belong to.