A Pokemon gains EVs as soon as its first EXP points, so you can start when an egg hatches or when your Pokemon is first caught (you might need to use an EXP Share for the first one, though). An EXP share passes on EV's as well as EXP Points. Extra stat points from EVs won't show up until the later stages of a Pokemon's development, so expect its stats to rise dramatically around lvl. 30 and up.
You just have to battle the right Pokemon that gives appropriate EV's (ex. Every Geodude you defeat will yield 1 DEF EV). You can collect a maximum of 510 EV's per Pokemon, 255 for each stat. For every 4 EVs, your Pokemon's stat will increase by one, so it's wise to have a 252/252/4 spread of EVs if possible. Be sure to keep track of which Pokemon you battle.