Is it ever mentioned how Val and Earl met, became friends, and came to live in Perfection?
According to the film's screenplay, Val and Earl are not originally from Perfection, but almost certain are from the general area, given their knowledge of the people and places around and nearby.
It stands to reason that they met on some job or other and decided that they liked each other enough to go into business, noting that their company sign is simply a hand-painted piece of wood stuck to the side of Earl's truck, so clearly this isn't the most formal of arrangements.
Val's bio describes him thusly;
This is VALENTINE MCKEE (25). Smart and good looking, Val has nevertheless managed to underachieve brilliantly. He coasts through life, following the path of least resistance -- which has brought him to this dubious rustic existence on the edge of civilization. But lately he's beginning to wonder why he hasn't accomplished more in his 25 years.
and Earl's bio has this to say;
Earl is a good-ol' boy who has lived his life just like Val, drifting from job to job. He knows why he hasn't accomplished anything, and often tries to impart his hard-won wisdom to Val, but the last thing the younger man wants is advice.