Caching of Internet content in caches local to users is beneficial to both users and the network, because it reduces retrieval times for the user as well as reduces load on the network. However, it comes at the cost of storage in the cache, which can be large, particularly when multimedia objects are cached. In this paper, we address the problem of caching multimedia objects such as audio and video streams, in a cost-distortion optimized way. That is, we seek caching policies that minimize the cost of both storage and transmission while minimizing the distortion seen by the user (or equivalently, maximizing the quality seen by the user). Simulation results demonstrate that caching in a cost-distortion optimized manner leads to significant improvements over the case where no caching is performed.