The GOMAD approach is a high-carb, high-insulin method of weight gain. A gallon of milk contains nearly 200gm of sugar. You will gain fat at the same time you gain muscle. Some bodybuilders like to gain weight in the off-season, then cut bodyfat for contests. A more paleo/primal approach would be to avoid insulin spikes (with resultant inflammation), and attempt to gain lean mass without the fat. This is a slower, but ultimately a more healthy process.
If you tolerate dairy products, you can utilize the fats and proteins from dairy without the carbs, by consuming cream, butter, ghee and whey protein. Of course, dairy is not paleo, but you're already consuming dairy.
You have to ask yourself whether you want to emphasize size or strength in your training. Strength comes from myofibrillar hypertrophy, while massive size comes from sarcoplasmic hypertrophy (edit, 5/22/2010, corrected due to Glenn's comment below). For strength, a low-rep program, such as Stronglifts 5x5 ( http://stronglifts.com/ ) would fit the bill. For size, a higher rep bodybuilding program is probably what you're looking for. Of course, you can combine these approaches if you like.
Finally, you can consider creatine supplements, which were discussed in an earlier thread ( http://paleohacks.com/questions/1037/creatine-and-paleo ).
