According to Serebii: The 'Strange Man', Giddy, (or at least his location in Mauville City Pokemon Center) is the source of most of the O-Powers:
Talk to [Giddy] and he will give you an O-Power, and then another. He'll then leave and be replaced by Hipster. He will give you three different O-Powers before he then leaves.
After that, Bard appears and will ask you to listen to songs, and give you two O-Powers.
A new man, Trader, then appears and offers to trade you Secret Base Decorations for a variety of simple items such as Potions and Poké Balls. In doing so, he too will give you an O-Power.
Finally, after he goes, another man, Storyteller, appears and tells you stories about yourself and gives you an O-Power.
At this point you should have all but one of the O-Powers. the last is only available after the Elite Four.
Speak to Storyteller again after beating the Elite Four and he will invite you up to his apartment in Mauville Hills. When there: (spoilers)
they will tell you that they are longing for someone to give power to, and learn of a powerless man across the hall. Speak to him and he will go to their apartment. Soon, the five men explain that they want to retire and they soon start to merge with the man and the man becomes Mr. Bonding.
Just before he leaves he gives you the final O-Power.