The following is needed:
Source: http://www.msdigest.net/2012/03/how-to-connect-to-office-365-with-powershell/
Then Follow this one if you're running a 64bits computer: I’m running a x64 OS currently (Win8 Pro).
Copy the folder MSOnline from (1) –> (2) as seen here
1) C:\Windows\System32\WindowsPowerShell\v1.0\Modules(MSOnline)
2) C:\Windows\SysWOW64\WindowsPowerShell\v1.0\Modules(MSOnline)
Source: http://blog.clauskonrad.net/2013/06/powershell-and-c-cant-load-msonline.html
Hope this is better and can save some people's time