1. Both get it, as long as they "showed up" in the battle; If someone holds an Exp. Share, he will also gain all EVs regardless of sending him into battle.
So, for instance, you have two Lillipups you'd wanna train for the ATTACK stat -- by killing patrats. You can both interchange them during the same battle so that both gain EVs on that one pokemon -- halving your training time. Now you have a Pikachu holding an EXP share, whether he participated in battle or not, he still gains that 1 attack EV from Patrat.
(this example does not count pokerus/EV boosting calculations; for that matter, it varies individually)
-----
2. EV training is like training for better stats. You don't really have to start with new pokemon, but you would most likely do because your current pokemon already have messed-up EVs. Also, they/you might be targeting for a beneficial nature, which makes starting over (breeding for a fresh, new poke) more likely to happen.
Doing the EV training post-game also allows access to any area. This makes it easier to find a perfect spot for your EV training.
-----
3. It doesn't happen immediately. Just keep count and make sure you're not losing track. It all adds up once you reach the final level. An explanation would be: your lillipup might not have actually gained an attack stat (naturally) at that level, and that 1 point was most likely from the EVs you've gained.
Unless you really train for more EVs, you won't notice big changes.
tip: EV training could be easier if you find/trade for a pokemon with Pokerus, too. Same goes with macho brace... I forgot about the individual items, but those were better than macho braces... try googling EV items. They reduce 252 pokemon -> 24 pokemon if you're doing things right.