Adding more data does not always help. However, you can get an estimate if more data will help you by the following procedure: Make a plot. On the $x$-axis is the amount of training examples, starting at one example per class going to wherever you are currently. The $y$-axis shows the error. Now you should add two curves: Training and test error. For low $x$, the training error should be very low (almost 0) and the test error very high. With enough data, they should be "about the same". By plotting those curves you can make an educated guess how much more data will give you how much improvement.
When doing this should I add data to both the training set and the test set?
Depends on what you want to achieve. If only getting a better classifier, then you can only add it to the training set. However, if you're doing this in a scientific setting this might be more difficult. (I assume that your test set is of reasonable size).
You might want to have a look at cross-validation.