Elliot-
I am not actively trying to gain weight presently (have to get my back working properly) but here are some suggestions.
1. 75% lean, grassfed ground beef. Can get it for about $4.10 a pound delivered (50 pounds).
http://www.grasslandbeef.com/StoreFront.bok
2. See what Neal said. I really like coconut oil.
3. If you can find them, free range eggs. Nice protein + fat shot. I've read lots of positives about eating them raw:
http://www.13.waisays.com/egg-yolk.htm
4. Not paleo, but unpasteurized, grassfed whole milk packs a lot of calories if you can tolerate it.