They do, you just have to search for them in flatlands or forests. They don't spawn in other places from what I've read.
Also, wouldn't it be nice if you could change the amounts of fairies your world can spawn like you could with DrZhark's Mo' creatures?
Another cute thing I just thought is making your fairies respond when you go to them.(like some happy face or some fairy way of greeting their leader) It makes them feel a bit more alive.
Just throwing in ideas that might be nice to have in here, even though I'm not sure how possible these ideas are.