"AES-256 encrypted storage" only means that the data is encrypted while at rest using AES-256. As to if the provider can read/decrypt ... that all depends on where the keys are stored. In many cases, providers who use encrypted storage do have the keys ... those keys are just kept securely in a location separate from the data. As popowich mentions, if the keys are never in the hands of the provider, then then provider "can't access the data".
However, if the encryption is done under the purview of a client-side application made by the provider, then you have to trust that the provider is not and can not use that application to get the keys based on code hidden in there now, or by code that may be introduced by a future software update. (i.e. under government mandate to insert something like how the US FBI wanted Apple to change the software in iPhone through the update channel so that the FBI could break in more easily).
So -- in most cases, there is some level of trust involved. If you are in full control of the keys yourself and are vetting the software used you can have more assurance of proper privacy.