Pokemon generally gain happiness as you play the game. However, there are specific occasions that cause happiness to increase:
When happiness reaches 220, the Pokemon will evolve the next time it levels up. In Gen 5, most Pokemon start with 70 happiness (list).
The fastest way to increase happiness is definitely EV-reducing berries, if you have them. If you don't, leveling up your Pokemon could be efficient if it is lower level. Otherwise, focus on vitamins and walking with your Pokemon a lot.
Source (if you're not playing Black/White, check this page to see the happiness table in your game)