TL;DR - Stay under 5,000 items for the entire library to get 100% of functionality
In addition to the 30 million documents per library you also need to be aware of the limit of 5,000 items per "view".
http://technet.microsoft.com/en-us/library/cc262787(v=office.15).aspx#ListLibrary
This particular limit can be changed in on-premise but in SharePoint Online it cannot. This means that Microsoft does not recommend having more than 5,000 folders or documents within a single folder. You can continue to nest folders but any single folder should not have more than 5,000 direct children (items or folders).
That being said... you will find there are limitations putting more than 5,000 documents into a single library no matter how efficient your foldering structure. This is because certain operations will apply to all items below a certain level and those operations (if they affect more than 5,000 items) will be throttled.
In my experience this includes:
- Adding a indexed property to the library that contains more than 5,000
- Changing permissions on t he library and or folder that contains more than 5,000