We study data-oblivious algorithms as a natural way to model privacy-preserving data outsourcing where a client, Alice, stores sensitive data at an honest-but-curious cloud storage server, Bob. The general approach involves obscuring the access patterns to a remote storage so that the manager of that storage, Bob, cannot infer information about its contents. Previous solutions typically involve costly amortized overheads for achieving this goal and involve potentially huge variations in access times, depending on when they occur. We show that efficient privacy-preserving data access is possible using a combination of probabilistic encryption, which directly hides data values, stateless oblivious RAM simulation, which hides the pattern of data accesses, and algorithms that are explicitly data oblivious.