To properly test your game you are going to need to go back to your requirements and review them. For each specific requirement you have to decide what procedure someone else would need to perform to prove to you that their software fulfilled that requirement. Write the procedure down, and move on to the next requirement. Be hypercritical, a skeptic's skeptic.
There are many formalized testing methodologies, but the basic need when testing is to ensure at least two things about any feature:
Does the program feature (operation, appearance, behavior) work the way it should, when it should?
Does the feature make something else not work the way it should, when it should?
Take your list of test procedures and run through your software answering those two questions. It is certainly a lot tougher to answer the second question—sometimes you will see something not working, only to find out later that it was some other feature that was causing the problem that you witnessed.
You will end up with a list of problems and probably some ideas about how to fix them. Fill your list up first before running off to repair the bugs, and then sit back and examine the list of problems to try to identify problems that may share the same root cause. You can possibly save much effort and time by fixing the root cause. Otherwise you might end up with a series of individual fixes and hacks, each of which only addresses a single issue, and each of which exposes another issue.
The phenomenon regression is caused by bug fixes that introduce new bugs or sometimes expose hidden bugs. Some software engineers dispute the idea of referring to exposing hidden bugs as regression, but to me it's a difference without a distinction. The result is the same.
To deal with regression, we need to run our tests after every bug-fixing session. Ask the same questions and look for the answers. If you have the time and patience (neither of which is commonly overly abundant), you should run your regression test after each bug fix. In other words, don't do your entire list of bug-fixing programming all at once and then jump back to your regression test. If new bugs have been introduced, it may be hard to find them, because the new code can be quite extensive.
You will also want to enlist a bevy of play testers because there can be more wrong with the game than simple (or not-so-simple) bugs. You need to ensure that the game is fun to play, and you need to ensure that the things you can do in the game have the effect you want them to have. If your game features an Easter egg hunt, you want to make sure that the players can actually find the hidden items. At the same time, you will probably want to make sure that the items aren't too easy to find. Achieving the balance in game play is why you want to use play testers.
When you and members of your development team are testing the software, this is usually referred to as the alpha test phase. Alpha testing can be considered complete when the development team's own testing is no longer finding problems. This, however, doesn't mean that testing is finished! You will eventually need to use people who have not been involved in the creation of the game for testing. Once you start letting outsiders play-test your game, you are now in the beta test phase. If the game is fun (and it will be, right?) then you should not have much trouble interesting people in being beta testers. And this will introduce a problem (it's a problem you want to have, but still a problem), which is that many beta testers will be playing the game and not testing it. While it is good for them to be enjoying themselves, you need them to take notes and record problems, issues, and general feelings about the way the game is played. You need these notes in order to know what to fix and what to change or add.
You should also consider creating test harnesses to use in your testing. These are programs that are designed to provide the inputs that will cause the various features of the game to be exercised. The testing software should log its output to a file, automatically take screen shots, or record whatever else that is needed so that you can review the results.
For example, you could create a special version of the client that will automatically run and play as if it were a real player. Then you could launch dozens of these clients in order to simulate client loads on the server.