Every time you battle a Pokémon, you are awarded one EV in whichever stat that Pokémon is set up to give. If you look at the equation for figuring out stats (not including HP):
Stat = Round down(
(( BaseStat * 2 + IV + Round down( EV/4 ) ) * Level/100 + 5 ) * P
)
you'll see two things. First, it takes 4 EV points to get a one point raise in your stat. Second, Only at level 100 do you get the full amount of EVs possible since, at anything less than level 100, you receive only a percentage based on your level.
So, usually, you don't start EV training until you've reached level 100. You can EV train to award EVs in any or all stats up to 510 total EVs. Different Pokémon award EVs in different stats, so you have to battle the ones that will raise only the stats you're training for.
There's a really detailed guide at GameFaqs for Ruby (the mechanics are the same for all the games since Ruby/Sapphire) that goes into incredible detail. It is the Advanced Trainer Guide by egervari. I'd post the URL but I haven't posted enough to get HTML turned on.