I had this problem while writing a feather system - here's the method I used.

First, generate a random distribution of points on each triangle - like Andrew says, weighted by area.

Then, to relax the points so they are evenly spaced on the surface, do a 2 step process.

1. Iterate over the points moving each point (in world space) a small distance away from its closest neighbors.
2. Snap all the points back to the closest point on the surface

Repeat those 2 steps until you are happy with the distribution. The points are well distributed when each point is surrounded by its neighbors at equal distances, and at that stage the repulsive force from each neighbor will nearly cancel out for a given point. So - as you iterate through the points, accumulate the magnitudes of those repulsion vectors and if the average is below a user defined threshold, stop refining.

It can be expensive to run those relax-and-snap steps several times because finding the closest neighbors means every point potentially considers every other point. You can use a kdTree to speed things up there. Also, finding the closest point on the mesh is slow for many tests by brute force. In my system I used another kdTree to store the triangles and that sped things up quite a bit, but its trickier than making a kdTree for points.

As an alternative to all that work, it might be worth looking at nParticles because they have some built in system to spread points evenly, and they can also be constrained to a surface. In this tutorial by Duncan Brinsmead he talks about attracting fluid nParticles to a glass surface, so that setup could theoretically be used to distribute points on a surface.

One of the problems I came up against (that will probably also be an issue with nParticles) was that for thin surfaces (like a birds wing) the repulsion algorithm was considering points on the other side of the wing. It would make the distribution very uneven on the surface as it was mainly trying to even things out in worldspace and those points on the other side were still close in worldspace. So I added in a test to make sure that only points on triangles with normals within some threshold angle would be considered.

EDIT Here's some code - I tried to make it self contained.

There's no Makefile because I use a different build system. Have a look at the file target.yml to see what maya libs are needed.

Once you have everything compiled open the scene test1.ma (from the examples folder.) It should look like this:

I'll add some better commenting and tidy up a bit as soon as I get time.