Paint layers are the most commonly used type of layers. If you've ever used layers in Photoshop or the Gimp, you'll be used to how they work. In short, a paint layer is a bitmap image (an image made up of many points of colour).
Because of this paint layers may occasionally be called pixel or bitmap layers.
Paint layers let you do many advanced effects such as smearing, smudging and distorting. This makes them the most flexible type of layer. The only real downside to paint layers is that they don't scale well when enlarged, and that the effects can't be edited once they're applied.
As long as you have enough resolution / size on your canvas though, and as long as you aren't going to need to go back and tweak an effect you created previously, then a paint layer is usually the type of layer you will want. If you click on the "New Layer" icon in the layers docker you'll get a paint layer. Of course you can always choose the "new layer" dropdown to get another type.