Gyroscopes and accelerometers both have inherent stability problems. Even the best gyros drift too much to be used by themselves, and accelerometers have enough noise in them to be problematic. Filtering solves these issues by combining the measurements of two devices (in my case a gyro and an accelerometer) into a more stable value, eliminating the drift of the gyro and the noise of the accelerometer. There are many different types of filters, many involving a lot of math. The best resource I found for this topic is this PDF that explains several different filtering options, and suggests an appropriate filter for self-balancing machines. The math is straightforward, it's explained in simple English, and most importantly it seems to work.
Most filters require tuning to work properly with your particular set up. The web is full of stories about people tuning their self-balancing robots for weeks. This is commonly a tiring process, as you have to tweak some settings, redeploy the code, and do some more testing.
With the skateboard, this wasn't as bad as I expected. Since the thing doesn't truly balance, you can get by with just a few tweaks here and there. In my case, the skateboard effectively worked on first try. Maybe I was just lucky, I'm not sure. I did play around with the filter for a while, but I'm not convinced I made it much better than it was initially.
I did play around with the formula a bit to try to get the right "feel" for performance. I ended up sticking with the original forumula, and heavily weighted the accelerometer reading versus the gyro.
Here's some test footage of the initial un-tuned algorithm as suggested by the above white paper.