Yeah, Pokémon do earn EVs in Colosseum. However, they will only earn EVs if they battle Pokémon when they have been de-shadowed. They won't earn EVs for anything they battled while they were shadowed.
There are only four Pokémon you can get that aren't shadow Pokemon when you first get them: Espeon, Umbreon, Plusle, and Ho-oh. Espeon and Umbreon earn a mandatory 2 Speed effort points and 2 HP effort points from battling Zigzagoon and Whismur before you can deposit either one into a PC and transfer it to a GBA cart for effort training once you beat the game.
Also, you can catch some Pokemon as female (anything that isn't genderless or all-male) and breed them now instead of having to wait for FRLG to get Ditto...